Помощь в учёбе, очень быстро...
Работаем вместе до победы

Приближенные методы решения задачи Штейнера на ориентированных графах

Диссертация: Приближенные методы решения задачи Штейнера на ориентированных графах
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Rabkin M. Efficient use of Genetic Algorithms for the Minimal Steiner Tree and Arborescence Problems with applications to VLSI Physical Design // Genetic Algorithms and Genetic Programming at Stanford. 2002. No. 1. P. 195−202. Gropl С., Hougardy S., Nierhoff Т., Prornel H. J. Lower bounds for approximation algorithms for the Steiner tree problem // Proceedings of the 27th International Workshop… Читать ещё >

Содержание

  • 1. Введение
    • 1. 1. Цели и задачи
    • 1. 2. Постановки задачи Штейнера
    • 1. 3. Применение
      • 1. 3. 1. УЬ81-проектироваиие
      • 1. 3. 2. Восстановление филогенетических деревьев
      • 1. 3. 3. Интерактивная телекоммуникация
    • 1. 4. Описание работы по главам
    • 1. 5. Основные определения и обозначения
  • 2. Состояние дел
    • 2. 1. Точные алгоритмы
      • 2. 1. 1. Алгоритм динамического программирования
      • 2. 1. 2. Сведение к задаче линейного программирования
    • 2. 2. Приближенные алгоритмы
      • 2. 2. 1. Алгоритм Такахаши-Мацуямы
      • 2. 2. 2. Приближенные алгоритмы основанные на линейном программировании
      • 2. 2. 3. Жадные алгоритмы
  • 3. Алгоритм к-кластерной оптимизации
    • 3. 1. Определение кластеров в графе
      • 3. 1. 1. Построение опорного дерева
      • 3. 1. 2. Разбиение на кластеры
    • 3. 2. Построение деревьев Штейнера на кластерах
    • 3. 3. Улучшение деревьев Штейнера на кластерах
    • 3. 4. Нахождение промежуточного полного дерева Штейнера
    • 3. 5. Улучшение промежуточного дерева Штейнера
    • 3. 6. Теорема о вычислительной сложности
  • 4. Приближенный метод 5* для задачи Штейнера на евклидовых графах
    • 4. 1. Алгоритм А* поиска кратчайшего пути
    • 4. 2. Задача Штейнера на концентрических окружностях
    • 4. 3. Алгоритм 5* на евклидовых графах
      • 4. 3. 1. Построение приближенного решения
      • 4. 3. 2. Построение множества терминальных подмножеств. Наивный метод
      • 4. 3. 3. Построение множества терминальных подмножеств. Метод «концентрических окружностей»
      • 4. 3. 4. Построение множества терминальных подмножеств. Обобщенный метод
      • 4. 3. 5. Теоретические результаты
  • 5. Вычислительные оптимизации
    • 5. 1. Общий обзор
    • 5. 2. Особенности реализации однопоточных алгоритмов
      • 5. 2. 1. Алгоритм динамического программирования
      • 5. 2. 2. /с-кластерный приближенный алгоритм
      • 5. 2. 3. Приближенный метод Б* на евклидовых графах
    • 5. 3. Параллелизация алгоритмов
      • 5. 3. 1. Параллелизация точного алгоритма решения
      • 5. 3. 2. Параллелизация алгоритма-кластерной оптимизации
      • 5. 3. 3. Параллелизация алгоритма аппроксимации S*
  • 6. Вычислительные результаты
    • 6. 1. Сравнение эффективности структур, реализующих приоритетную очередь
    • 6. 2. Сравнение эффективности-кластерного метода с другими известными
    • 6. 3. Сравнение эффективности метода S* с другими известными
    • 6. 4. Сравнение быстродействия однопоточных и параллельных реализаций методов
      • 6. 4. 1. Метод динамического программирования
    • 6. 5. Метод к-кластерной оптимизации
    • 6. 6. Метод 5*
  • 7. Результаты и
  • выводы

Приближенные методы решения задачи Штейнера на ориентированных графах (реферат, курсовая, диплом, контрольная)

Задача Штейнера, или задача о минимальном дереве Штейнера, названная в честь швейцарского математика Якова Штейнера, является задачей комбинаторной оптимизации. Она может быть сформулирована в различных постановках, однако в любой задаче Штейнера, независимо от конкретной формулировки: на евклидовой плоскости или в более общей, графовой, форме, требуется найти кратчайшую сеть, связывающую заданное множество вершин, имея возможность использовать промежуточные вершины.

1.1. Цели и задачи.

Основными целями данной работы является: а) Определить степень востребованности и применимости данной конкретной постановки задачи Штейнера, и актуальности ее исследования. б) Исследовать и проанализировать имеющиеся способы приближенного решения задачи Штейнера на ориентированных графах, выделить основные направления исследования и перспективы дальнейшего исследования в различных направлениях. в) Разработать методы для приближенного решения задачи Штейнера на ориентированных графах в общей постановке, и в различных специальных случаях, применимых на практике. г) Для разработанных методов в случае возможности найти точную теоретически обоснованную оценку трудоемкости и коэффициента аппроксимации. д) Экспериментально сравнить разработанные методы с наиболее известными и часто применяемыми приближенными методами. е) Определить возможность параллелизации представленных методов и если она есть, разработать параллельные реализации алгоритмов. ж) Провести экспериментальные сравнения однопоточных и параллельных версий представленных алгоритмов. з) Сделать выводы о возможности и целесообразности применения данных методов на практике, а также возможных дальнейших улучшений этих методов.

1., Джонсон Д. Вычислительные машины и труднорешае-мые задачи. М.: Мир, 1982.

2. Диниц Е. А. Экономические алгоритмы нахождения кратчайших путей в сетях / под ред. Ю. С. Попкова и Б. JI. Шмульяна, Институт Системного Анализа, М., 1978.

3. Романовский И. В. Дискретный анализ. СПб.: Невский ДиалектБХВ-Петербург, 2003.

4. Кристофидес Н. Теория графов: алгоритмический подход. М.: Мир, 1978.

5. Alexander М., Cohoon J. P., Ganley J. L., and Robins G. An architecture-independent approach to FPGA routing based on multi-weighted // EURO-DAC '94 Proceedings of the conference on European design automation, 1994.

6. Alexander M., Robins G. An architecture-independent unified approach to FPGA routing / Dept. of Computer Science, Univ of Virginia, 1993.

7. Alexander M. J., Robins G. New Perfomance-Driven FPGA Routing Algorithms / Technical Report, 1994.

8. Andrews G. Foundations of Multithreaded, Parallel, and Distributed Programming. Addison-Wesley, ISBN 0−201−35 752−6, 2000.

9. Arora S., Barak B. Computational Complexity A Modern Approach. Cambridge, ISBN 978−0-521−42 426−4, 2009.

10. Arora S. Polynomial-Time Approximation Schemes for Euclidean TSP and other geometric problems /7 Journal of the ACM (JACM), 1998. No. 45(5). P. 753−782.

11. Awerbuch В., Azar Y., Gawlick E. Maximal Dense Trees and Competitive On-line Selective Multicast (Extended Abstract) // Computer, 2007.

12. Bishop P., Warren N. Lazy instantiation: Balancing performance and resource usage. 1999. Электронный ресурс. URL: http: / / www. j avaworld. com/j avaworld/j avatips/j w-j ava, tip6 7. html (дата обращения: 24.02.2010).

13. Charikar M., Chekuri C., et. al. Approximation algorithms for directed Steiner problems // Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 1998. P. 192−200.

14. Charikar M. Approximation Algorithms for Directed Steiner Problems. Journal of Algorithms, 1999. No. 33(1). P. 73−91.

15. Cherkassky B. V., Goldberg A. V., Silverstein C. Buckets, heaps, lists, and monotone priority queues /,/ Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, 1997. P. 83−92.

16. Chin L. L., Chuan Y. T., Lee R. The Full Steiner Tree Problem in Phylogeny // Computing and Combinatorics, 2002.

17. Cormen T., Leiserson C., Rivest R., and Stein C. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001.

18. Dearagao M., Uchoa E., and Werneck R. Dual Heuristics on the Exact Solution of Large Steiner Problems // Electronic Notes in Discrete Mathematics, 2001. Vol. 7. P. 150−153.

19. Denardo E., Fox B. Shortest-route methods: 1. reaching, pruning, and buckets // Operations Research, 1979.

20. Dial R. B. Algorithm 360: Shortest Path Forest with Topological Ordering // Comm. ACM, 1969. No. 12. P. 632−633.

21. Dijkstra E. W. A note on two problems in connexion with graphs // Numerische Mathematik, 1959. No. 1. P. 269−271.

22. Edmonds J. Optimum branchings // Journal of Research of the National Bureau of Standards B. 71B, 1967. P. 233−240.

23. Fredman M. L., Tarjan R. E. Fibonacci heaps and their uses in improved network optimization algorithms // Journal of the ACM (JACM), 1987. Vol. 34, No. 3, P. 596−615.

24. Gafni E. M., Bertsekas D. P. Path assignment for virtual circuit routing // Proceedings of the symposium on Communications Architectures & Protocols (SIGCOMM '83), 1983.

25. Gamma E., Helm R., Johnson R., Vlissides J. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, 1994.

26. Goldberg A. V., Shortest path algorithms: Engineering aspects // Algorithms and Computation, 2001. P. 502−513.

27. Goldberg A. V., Silverstein C. Implementations of Dijkstra, Algorithm Based on Multi-Level Buckets. Network optimization, 1997. P. 292 327.

28. Goldberg A. V. A practical shortest path algorithm with linear expected time // SIAM Journal on Computing, 2008. Vol. 37. P. 1637.

29. Gropl С., Hougardy S., Nierhoff Т., Prornel H. J. Lower bounds for approximation algorithms for the Steiner tree problem // Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, 2001.

30. Hanan M. On Steiner’s problem with rectilinear distance // SIAM Journal Of Applied Mathematics, 30(1), 1966. P. 104−114.

31. Hart P. E., Nilsson N. J., Raphael B. A formal basis for the heuristic determination of minimum cost paths // IEEE transactions on Systems Science and Cybernetics, 1968. No. 4. P. 100−107.

32. Hillar G. Professional Parallel Programming with Сф. Wiley Publishing, 2010.

33. Hwang F. K. A Linear Time Alorithm for Full Steiner Trees. Operations Research Letters, 1986. No. 4(5). P. 235−237.

34. Kahng А. В., Robins G. A New Class Of Iterative Steiner Tree Heuristics With Good Performance // IEEE Transactions Of Computer-Aided Design of Integrated Circuits And Systems, 1992. No. 11(7). P. 893−902.

35. Krazit. T. Intel pledges 80 cores in five years. CNET, 2006. Электронный ресурс. URL: http://news.cnet.com/.

36. Molle D., Richter S., and Rossmanith P. A faster algorithm for the Steiner tree problem. STACS 2006, 2006. No. 1. P. 561−570.

37. McGregor J. Mobile Processor Review / Technical Review, InStat, 2009.

38. Melkonian V. New primal-dual algorithms for Steiner tree problems // Computers & Operations Research. 34, 2007. P. 2147−2167.

39. Polzin T., Daneshmand S. V. A comparison of Steiner tree relaxations // Discrete Applied Mathematics, 2001. No. 112. P. 241−261.

40. Polzin T., Daneshmand S. V. Improved algorithms for the Steiner problem in networks // Discrete Applied Mathematics, 2001. No. 112. P. 263−300.

41. Polzin T., Daneshmand S. V. Partitioning techinques for the Steiner problem / Research Report MP1−1-2001;1−006. Max-Planck-Institut fur Informatik, Stuhlsatzenhausweg 85, 66 123 Saarbrucken, Germany, 2001.

42. Promel H. J., Steger A. The Steiner tree problem: a tour through graphs, algorithms, and complexity. Vieweg I Teubner, 2002.

43. Rabkin M. Efficient use of Genetic Algorithms for the Minimal Steiner Tree and Arborescence Problems with applications to VLSI Physical Design // Genetic Algorithms and Genetic Programming at Stanford. 2002. No. 1. P. 195−202.

44. Rajagopalan S., Vazirani V. V. On the bidirected cut relaxation for the metric Steiner tree problem / SODA, — 2000.

45. Rayward-Smith. V. The computation of nearly minimal Steiner trees in graphs // International Journal of Mathematical Education in Science and Technology, 1983. No. 14.1.

46. Richter J. CLR via C# (3rd Edition). Microsoft Press, 2010.

47. Robins G., Zelikovsky A. Improved Steiner Tree Approximation in Graphs // Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, 2000.

48. Santos M., Uchoa E. Distributed Dual Ascent Algorithm for the Steiner Problem in Graphs Sequential Wong’s Dual Ascent Algorithm // Production Engineering, 2006. P. 1−14.

49. Smith J. M., Lee D. T., Liebman J. S. An 0(nlogn) heuristic for Steiner minimal tree problems in euclidean metrics // Networks, 1981. No. 11. P. 23−29.

50. Stroustrup B. The C++ Programming Language (Third Edition and Special Edition). Addison-Wesley, 2004.

51. Sutter H. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software // Dr. Dobb’s Journal, 2005. No. 30(3),.

52. Takahashi H., Matsuyama A. An Approximate Solution for the Steiner Problem In Graphs. Math. Japonica, 1980. No. 6. P. 573−577.

53. Troelsen A. Pro C# 2010 and the .NET 4 Platform, 5th Edition. APRESS, 2010.

54. Vuillemin J. A data structure for manipulating priority queues // Communications of the ACM, 1978. Vol. 21, No. 4. P. 309−315.

55. Wagner R. A. A shortest path algorithm for edge-sparse graphs // J. Assoc. Comput. Math., 1976. No. 23. P. 50−57.

56. Wong R. T. A dual ascent approach for Steiner tree problems on directed graphs // Math. Programming, 1984. No. 28. P. 271−287.

57. Zachariasen M., Winter P. Concatenation-Based Greedy Heuristics for the Euclidean Steiner Tree Problem / Technical Report 97/20, DIKU, Department of Computer Science, University of Copenhagen, 1997.

58. Zachariasen M. Rectilinear Full Steiner Tree Generation / Technical Report 97/20, DIKU, Department of Computer Science, University of Copenhagen, 1997.

59. Zelikovsky A. 11/6-approximation algorithm for the Steiner problem on graphs // Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity. Ann. Disc. Math., 1992. P. 351−354.

60. Zelikovsky A. A Series of Approximation Algorithms for the Acyclic Directed Steiner Tree Problem /./ Framework, 1997. P. 1−10.

61. Zelikovsky A. An 11/6-approximation algorithm for the network steiner problem // Algorithmica, 1993. No. 9. P. 463−470.

62. Zelikovsky A. Better Approximation Algorithms for the Network and Euclidean Steiner Tree Problems / Technical report, Kishinev, 1995.

63. Zelikovsky A. The last achievements in Steiner tree approximations // CSJM v. l, n. l (1), 1993.

64. Zhang Y. Virtual Circuit Routing. Class Report (October 2003), 2003. P. 1−11.

65. SteinLib Testdata Library, 2009. Электронный ресурс. URL: http://steinlib.zib.de/steinlib.php (дата обращения: 27.05.2009).

66. The Computer Language Benchmarks Game. Электронный ресурс. URL: http://shootout.alioth.debian.org (дата обращения :0109.2008).

Показать весь текст
Заполнить форму текущей работой

Пора сдавать?