2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Алгоритмы на графах. Литература.
Сообщение28.11.2017, 16:56 
Аватара пользователя


26/05/12
1534
приходит весна?
Посоветуйте, пожалуйста, литературу посвящённую алгоритмам на графах. Желательно что-нибудь доступное, без заумной математики и с примерами кода. Можно на английском. Поиск путей (в том числе и кратчайшего) наверняка не единственная задача, связанная с графами. Хотелось бы ознакомиться с тем, что народ до сих пор напридумывал в этой области. Заранее очень благодарен.

 Профиль  
                  
 
 Re: Алгоритмы на графах. Литература.
Сообщение28.11.2017, 17:01 


14/01/11
2916
Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение.

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


26/05/12
1534
приходит весна?
Спасибо за быстрый ответ. Скачаю, ознакомлюсь.

Можно сразу вопрос до кучи, чтобы темы не плодить? У меня имеется планарный граф и я хочу найти все возможные различные пути из вершины А в вершину Б. Под различными понимаются такие пути, каждый из которых содержит вершину, которую не содержит другой путь. Если же имеется два пути, допустим 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 
Аватара пользователя


31/10/08
1244
Окулов С.М.-Программирование в алгоритмах. БИНОМ. Лаборатория знаний (2014)

 Профиль  
                  
 
 Re: Алгоритмы на графах. Литература.
Сообщение29.11.2017, 04:04 


01/05/17
50
Где я?
"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 
Аватара пользователя


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

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

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


11/06/12
10390
стихия.вздох.мюсли
Paragraph в сообщении #1270078 писал(а):
"Algorithms on Trees and Graphs", Gabriel Valiente, Springer 2002.
http://b-ok.org/book/2099958/2128a6.

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


26/05/12
1534
приходит весна?
Aritaborian, спасибо.

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

 Профиль  
                  
 
 Re: Алгоритмы на графах. Литература.
Сообщение01.12.2017, 04:43 


01/05/17
50
Где я?
Цитата:
Paragraph в сообщении #1270078 писал(а):
"Algorithms on Trees and Graphs", Gabriel Valiente, Springer 2002.
http://b-ok.org/book/2099958/2128a6.

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

 Профиль  
                  
 
 Re: Алгоритмы на графах. Литература.
Сообщение01.12.2017, 05:45 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Paragraph в сообщении #1270595 писал(а):
Спасибо за ссылку!
B@R5uk в сообщении #1270246 писал(а):
Aritaborian, спасибо.
Места надо знать ;-D

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group