Перечень ссылок
по теме: «Исследование существующих алгоритмов решения транспортных задач в ГИС»
Выполнила: Ганущак Н.К.
В процессе написания работы были использованы следующие материалы:
- Evaluation of Route Finding Methods in GIS Application [http://www.gisdevelopment.net/technology/gis/ma03202pf.htm]
Статья, в которой описываются результаты проведенных ранее исследований алгоритмов нахождения кратчайшего пути
(алгоритм Дейкстры, Генетический и Эвристический алгоритмы) на реальных транспортных сетях с использованием ГИС технологий.
- Алгоритмы поиска кратчайших путей. Электронный учебник по информатике, школа №9 им. А.С.Пушкина, г.Пермь
[http://school9.perm.ru/Tutorial/Graph/chapter2/shortest_way.htm]
Часть главы из электронного учебника по информатике, описывающей алгоритмы кратчайших путей, в которой даются базовые понятия теории графов, а также приводится таблица,
в которой содержится информация о существующих алгоритмах поиска кратчайших путей, их скорости выполнения при различном числе узлов сети.Сделаны выводы по каждой таблице и по результатам тестов в целом,
какие алгоритмы наиболее быстро работают при заданных условиях и поставленных задачах
- Алгоритм Флойда. Электронный учебник по информатике, школа №9 им. А.С.Пушкина, г.Пермь [http://school9.perm.ru/Tutorial/Graph/chapter2/shortest_way/floyd.htm]
Описание и схема данного метода в простой и доступной форме.
- Алгоритм Дейкстры [http://algolist.manual.ru/maths/graphs/shortpath/dijkstra.php]
Данная страница содержит описание схемы алгоритма Дейкстры, а также советы по реализации этого метода. Можно обсудить предложенный материал на форуме
- Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures
[http://www.swt.edu/~fz01/]
Статья, в которой описаны исследования трех алгоритмов нахождения кратчайшего пути (Ростущий граф (graph growth algorithm) и две
модификации алгоритма Дейкстры - с апроксимальными ведрами (approximate buckets) и с двойными ведрами (double buckets)).
Содержит описание схем алгоритмов, иллюстрации и примеры процедур реализации алгоритмов.Проведен глубокий анализ существующих исследований по данной теме.
Кроме того, предоставлен достаточно большой перечень ссылок по теме исследования алгоритмов кратчайшего пути.
- Dijkstra's algorithm [http://en.wikipedia.org/wiki/Dijkstra's_algorithm]
Статья из электронной энциклопедии, в которой объясняется принцип и схема работы алгоритма Дейкстры,
а также рассказывается о возможных модификациях метода. Приведен перечень ссылок,
по которым можно найти дополнительную информацию по данной теме.
- Королёва Ирина. Кратчайшие пути [http://gip-102irina.narod.ru/List.htm]
Рассмотрены три
наиболее эффективных алгоритма нахождения кратчайшего пути: 1) алгоритм Дейкстры (используется для нахождения
оптимального маршрута между двумя вершинами), 2) алгоритм
Флойда (используется для нахождения оптимального маршрута между всеми парами
вершин) 3) алгоритм Йена (используется для нахождения
k-оптимальных маршрутов между двумя вершинами).
- Романовский И.В. Дискретный анализ: Учебное пособие для студентов, специализирующихся на прикладной математике и информатике. — 3-е изд., перераб. и доп. — СПб.: Невский Диалект; БХВ-Петербург, 2003
Теория графов. Задача о кратчайшем пути. Алгоритм Левита. Алгоритм Уоршелла-Флойда
- Колодинская Е.В.,Скляренко О.А. Сетевое моделирование:основные методы и программная реализация [http://www.vb.kiev.ua/magazine/2004/01/cm200301_11.pdf]
Рассмотрены три сетевых метода: алгоритм нахождения критического пути, алгоритм
минимального остовного дерева и алгоритм нахождения кратчайшего пути.Алгоритмы были реализованы в Borland Delphi 6. Есть иллюстрации, листинг процедур, рассмотрены примеры применения.
- Решение транспортных задач в MapInfo - геоинформационные системы ESTI MAP [http://www.esti-map.ru/magellan.htm]
Описание и характеристики ChronoVia – модуля для поиска оптимальных путей в сети,
и ChronoMap – модуля для построение зон транспортной доступности.
- NetEngine [http://www.dataplus.ru/Soft/ESRI/NetEngine/Index.htm]
Этот программный пакет
предназначен для создания функций сетевого моделирования, нахождения пути (маршрута) и отслеживания сетевой топологии.
С его помощью можно моделировать любые сети, в том числе абстрактные. Краткое описасние программных функций
- Модуль Network Analyst [http://www.dataplus.ru/Soft/ESRI/ARCVIEW/Network.htm]
С помощью Network Analyst решается задача поиска
ближайшего пункта обслуживания а также выполняется определение зон обслуживания(доступности). Краткое описасние программных функций
Описания алгоритмов нахождения кратчайший путей и методов решения других задач анализа сети:
- Пути с минимальным количеством промежуточных вершин [http://it.kgsu.ru/TI_11/tgr_010.html]
Постановка задачи. Описание волнового алгоритма. Доказательство корректности этого алгоритма
- Кратчайшие пути[lhttp://ait.ustu.ru/disciplines/discret/el_ucheb/Graf/part511.html]
Постановка задачи. Рассмотрен алгоритм Декстры с примером
- Алгоритм поиска кратчайшего пути [http://algolib.narod.ru/Graph/Path.html]
Рассматривается на примере действия алгоритма Дейкстры
- Алгоритм Дейкстры - Программирование от RIN.RU [http://program.rin.ru/razdel/html/686.html]
Описание алгоритма. Возможность обсудить информацию на форуме, в чате
- Алгоритм Дейкстры. Столлингс В. Современные компьютерные сети.2-е изд.-СПб:Питер,2003.-783с. [http://www.uran.donetsk.ua/~masters/2005/fvti/soldatova/library/dijkstra.htm]
Описание алгоритма
- Dijkstra's algorithm [http://www.nist.gov/dads/HTML/dijkstraalgo.html]
Описание алгоритма. Ссылки на другие алгоритмы
- Dijkstra's algorithm [http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm]
Описание методологии алгоритма
- Алгоритм Дейкстры для кратчайшего пути в графе [http://bib.com.ua/info860.html]
Объяснение Алгоритма Дейкстры нахождения кратчайшего пути в графе (скачать или получить письмом)
- Finding shortest path [Archive] - AKB Forums[http://forum.armkb.com/archive/index.php/t-3366.html]
Форум. Рассматривается "волновой" алгоритм
- Задача поиска пути наименьшей длины [http://www.tisbi.ru/resource/lib/graph/Teor1.htm]
Основные понятия теории графов. Постановка задачи. Алгоритм решения. Пример.
- Графы.Кратчайшие пути [http://rain.ifmo.ru/cat/view.php/vis/graph-shortest-paths]
Описание алгоритмов Джонсона, Дейкстры, Левита и др.
- Построение графа наименьшей длины [http://www.sumdu.edu.ua/cources/mo/!_dop_r/t_86.html]
Описавние способа построения с формулами и рисунками
- ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ: Бизнес-словарь [www.businessvoc.ru/bv/Term.asp?word_id=4958]
Дано определение, что это такое
- ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ (shortest route problem) [http://www.mtmlogistika.com/termslib/shortest_route_problem.htm]
Справочная информация (определение)
- Задача о кратчайшем пути [http://yas.yuna.ru/]
Определение, комментарий, ссылки на другие термины по теме
- Задача о кратчайших путях [http://algolist.manual.ru/maths/graphs/shortpath/]
Ссылки на описание нескольких алгоритмов кратчайших путей
- Задача о кратчайших путях [http://www.ishodniki.ru/list/info.php]
Рассмотрены различные варианты задачи нахождения кратчайших путей, в том числе - различных условиях на данные.(скачать беспл.)
-Волновой алгоритм
-Алгоритм Форда-Беллмана
-Алгоритм Флойда
-Алгоритм Дейкстры
-Нахождение k кратчайших путей в графе.
- Нахождение кратчайших путей в графе [http://www.allmath.ru/highermath/algebra/diskret-dubna/Ll6_9.html]
Рассмотрены теоретические основы различных методов нахождения кратчайших путей в графе, в том числе и алгоритм Форда-Беллмана
- Обобщенная задача о кратчайшем пути. Р.А. Акбердин, Ш.А. Зайнуллина
[http://www.nkzu.edu/NKZU/FIT/mat/publisher/statiaARA.htm]
Постановка задачи. Решение с рисунками и примерами. Дан список литературы по данной теме
- Редкие(комбинированные) задачи на графы. Форум [http://www.progz.ru/forum/viewtopic.php]
Обсуждение темы. Полезные советы
- Постановка транспортної задачі [http://www.ducc.donetsk.ua/mp/04/04.htm]
Способы решения транспортных задач и примеры на украинском языке
Описания исследований иностранных ученых:
- GIS-based Object Model - Centre for Logistics and Freight Transport [http://www1.ctt.dtu.dk]
Описание проекта, разработанного на платформе ArcInfo GIS для решения задач сетевого анализа
- Experimental Evaluation of Dynamic All Pairs Shortest Path Algorithms. Camil Demetrescu, Stefano Emiliozzi, and Giuseppe F. Italiano [http://www.dis.uniroma1.it/~demetres/experim/dsp/]
[download pdf, 212KB]. C implementations of several static and dynamic algorithms for single-source and all-pairs shortest path problems, generators of random and hard inputs, real test sets in Dimacs and XML format...
- Fastest path problems in dynamic transportation networks [http://www.husdal.com/gis/print/research.htm]
Исследование алгоритмов для динамических и статических сетей
- Shortest Path Algorithms: An Evaluation Using Real Road Networks. F. Benjamin Zhan, Charles E. Noon [http://portal.acm.org/citation.cfm?id=768142&dl=GUIDE&coll=GUIDE]
Кратко об исследовании. Ссылки на работы по данной теме
- Fastest Shortest Path Algorithms on Road Networks.
[http://uweb.txstate.edu/~fz01/sp_algorithms.htm]
Ссылки на исследование в данной области
- Shortest Paths Algorithms: Theory And Experimental Evaluation (1993) [http://citeseer.ist.psu.edu/cherkassky93shortest.html]
Ссылки на множество работ по данной теме и не только
Описания проведения и результатов исследований в различных областях (чтобы понять, что есть исследование и в какой форме нужно получить результаты):
- Система исследования алгоритмов поиска оптимальных маршрутов движения транспортных средств. Золотовицкий А. В., Михеева Т. И.
[http://ic.samaranet.ru/other/research-system-find-algorithms.htm]
- Моделирование и исследование алгоритмов динамического управления потоками сообщений в информационно-вычислительных сетях.
Тукубаев З.Б., Тукубаев Б.З.
[http://www.nsc.ru/ws/show_abstract.dhtml]
- Исследования алгоритмов обучения модели обратного распространения.Ямникова И.В., Снежко Е.М. [http://www.dgma.donetsk.ua/~ek/sc/neyro2002/2002/art06.htm]
- Исследование алгоритма автоматической классификации на основе критерия согласия. Чекал Е.Г., Чичев А.А.
[http://usca.ulx.ru/depart_inf/publications/publications_2.html]
- Исследование алгоритмов автоматической идентификации точек на паре видеоснимков. Быков Л. В., Ессин А. С., Макаров А. П.
[http://www.sibrcc.ru/info/article.php?show_art=yes&id_article=15]
- Результаты исследований алгоритмов параллельных вычислений прямой и обратной задач манипулятора
[http://nit.miem.edu.ru/cgi-bin/article?id=67]
- Исследование алгоритмов адаптивной маршрутизации на примере транспортной сети г.Макеевки. Слесарь Е. С. [http://www.uran.donetsk.ua/~masters/2005/kita/slesar/diss/index.htm]
- Інформаційні та управляючі системи [http://users.kpi.kharkov.ua/cutting/Forums/mc2004_01.htm]
Перечень докладов форума MicroCAD 2004. Интересно - Раскин Л.Г., Зинченко И.В., Украина, Харьков
РАЦИОНАЛЬНОЕ ПЛАНИРОВАНИЕ ПЕРЕВОЗОК В СИСТЕМЕ «ПОСТАВЩИК –ПРОМЕЖУТОЧНЫЕ ЦЕНТРЫ – ПОТРЕБИТЕЛИ» и др.
На этих сайтах можно найти много интересных бардовских песен различных авторов:
- Все о бадрах. Авторская песня [http://www.bards.ru/]
- Авторская песня: Тексты и аккорды песен [http://u-sergeya.hotbox.ru/autor.htm]
- Поиск артистов и композиций [http://www.lyricfind.ru/]