2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Алгоритмы на графах. Литература.
Сообщение28.11.2017, 16:56 
Аватара пользователя
Посоветуйте, пожалуйста, литературу посвящённую алгоритмам на графах. Желательно что-нибудь доступное, без заумной математики и с примерами кода. Можно на английском. Поиск путей (в том числе и кратчайшего) наверняка не единственная задача, связанная с графами. Хотелось бы ознакомиться с тем, что народ до сих пор напридумывал в этой области. Заранее очень благодарен.

 
 
 
 Re: Алгоритмы на графах. Литература.
Сообщение28.11.2017, 17:01 
Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение.

 
 
 
 Re: Алгоритмы на графах. Литература.
Сообщение28.11.2017, 17:45 
Аватара пользователя
Спасибо за быстрый ответ. Скачаю, ознакомлюсь.

Можно сразу вопрос до кучи, чтобы темы не плодить? У меня имеется планарный граф и я хочу найти все возможные различные пути из вершины А в вершину Б. Под различными понимаются такие пути, каждый из которых содержит вершину, которую не содержит другой путь. Если же имеется два пути, допустим S и R, причём множество вершин пути S является подмножеством вершин пути R, то такие два пути являются эквивалентными, и в ответ выбирается, разумеется, самый короткий путь S.

Например, вот эти два пути различны:
Код:
    #####           #####
    #...#           #...#
    #...#           #...#
  ###...##        ###...##
  #......#        #......#
###.#.##.###    ###.#.##.###
#...#.##...#    #...#.##...#
#.S>>>>>>E.#    #.S>>v.>>E.#
#####.#....#    #####v#^...#
    #...####        #>>^####
    #####           #####


А вот здесь первые три эквивалентны, причём предпочтение отдаётся самому левому, в то время как четвёртый отличается от первых трёх:
Код:
    #####           #####           #####           #####
    #...#           #...#           #...#           #...#
    #...#           #...#           #...#           #...#
  ###...##        ###>v.##        ###.>v##        ###>>v##
  #..>>>v#        #..^>>v#        #..>^>v#        #..^.>v#
###.#^##v###    ###.#^##v###    ###.#^##v###    ###.#^##v###
#...#^##v..#    #...#^##v..#    #...#^##v..#    #...#^##v..#
#.S>>^..>E.#    #.S>>^..>E.#    #.S>>^..>E.#    #.S>>^..>E.#
#####.#....#    #####.#....#    #####.#....#    #####.#....#
    #...####        #...####        #...####        #...####
    #####           #####           #####           #####


В каком направлении копать?

 
 
 
 Re: Алгоритмы на графах. Литература.
Сообщение28.11.2017, 21:16 
Аватара пользователя
Окулов С.М.-Программирование в алгоритмах. БИНОМ. Лаборатория знаний (2014)

 
 
 
 Re: Алгоритмы на графах. Литература.
Сообщение29.11.2017, 04:04 
"Algorithms on Trees and Graphs", Gabriel Valiente, Springer 2002. ISBN 978-3-662-04921-1
доступно написана и использует literate programming, т.е. код, его спецификация и документация представляют собой единый документ. Не уверен, есть ли где pdf для "ознакомления" (у меня физическая копия). Если найдете pdf, буду признателен, если дадите знать в ЛС.

 
 
 
 Re: Алгоритмы на графах. Литература.
Сообщение29.11.2017, 11:52 
Аватара пользователя
Pavia в сообщении #1270023 писал(а):
Окулов С.М.-Программирование в алгоритмах. БИНОМ. Лаборатория знаний (2014)
Большое спасибо! В числе прочего, в главе про комбинаторику нашёл решение задачи, над которой давно ломал голову: восстановить перестановку по её порядковому номеру. Решение на столько простое, что мне даже стыдно, что я сам не смог додуматься.

Paragraph, предложенную вами книгу при быстром осмотре в электронном виде не нашёл. Когда будет доступ к безлимитному интернету попробую более тщательный поиск.

 
 
 
 Re: Алгоритмы на графах. Литература.
Сообщение29.11.2017, 12:02 
Аватара пользователя
Paragraph в сообщении #1270078 писал(а):
"Algorithms on Trees and Graphs", Gabriel Valiente, Springer 2002.
http://b-ok.org/book/2099958/2128a6.

 
 
 
 Re: Алгоритмы на графах. Литература.
Сообщение29.11.2017, 23:21 
Аватара пользователя
Aritaborian, спасибо.

Для задачки выше, я таки построил некий алгоритм. Он находит все возможные различные пути из заданной точки в каждую другую. Для графа, получающегося из карты на картинке выше для разных точек выходит от 1000 до 5000 вариантов. Вот, думаю, не многовато ли?

 
 
 
 Re: Алгоритмы на графах. Литература.
Сообщение01.12.2017, 04:43 
Цитата:
Paragraph в сообщении #1270078 писал(а):
"Algorithms on Trees and Graphs", Gabriel Valiente, Springer 2002.
http://b-ok.org/book/2099958/2128a6.

Спасибо за ссылку!

 
 
 
 Re: Алгоритмы на графах. Литература.
Сообщение01.12.2017, 05:45 
Аватара пользователя
Paragraph в сообщении #1270595 писал(а):
Спасибо за ссылку!
B@R5uk в сообщении #1270246 писал(а):
Aritaborian, спасибо.
Места надо знать ;-D

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group