Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 26.05.2010, 20:50
гость

 
Сообщений: n/a

Поиск кратчайшего пути
Имеется простой многоугольник U. В нем находятся еще несколько простых многоугольников P1, P2, ..., Pn которые между собой не пересекаются. Имеются две точки A и B которые принадлежат многоугольнику U, но не принадлежат многоугольникам Pi, i =1,..n. Найти кратчайший путь от точки A до точки B, который бы не пересекал стороны любого из многоугольников.

Пример: http://s002.radikal.ru/i197/1005/c6/87432dd23cf6.jpg
  #2  
Старый 27.05.2010, 00:56
гость

 
Сообщений: n/a

Классическая задача выч геометрии. Строишь граф видимости и ищешь в нем кратчайший путь любым алгоритмом для графов. Вершины графа - вершины твоих полигонов + начальная и конечная точка.
  #3  
Старый 27.05.2010, 17:20
гость

 
Сообщений: n/a

сложность алгоритма графа видимости n^2. Мне нужен алгоритм, который находит путь за линейное время
  #4  
Старый 27.05.2010, 18:34
гость

 
Сообщений: n/a

ну так ищи и читай статьи

http://scholar.google.com/scholar?hl...-8&sa=N&tab=ws
  #5  
Старый 27.05.2010, 18:39
гость

 
Сообщений: n/a

вот например

Guibas et al. Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons
  #6  
Старый 27.05.2010, 18:49
гость

 
Сообщений: n/a

да я бы и не писал здесь, если бы нашел. Я искал очень долго и на русском языке и на английском и находил максимум намеки. Описаний алгоритмов не было. Сюда написал только потому что потерял надежду найти их =(
  #7  
Старый 27.05.2010, 19:30
гость

 
Сообщений: n/a

большое всем спасибо) вот даже ссылочка на издание. Теперь есть шанс что получу красный диплом =)) http://openlibrary.org/works/OL12295...imple_polygons
  #8  
Старый 27.05.2010, 19:45
гость

 
Сообщений: n/a

а чё, если бы за n^2 решил был бы не красный?
  #9  
Старый 27.05.2010, 19:57
гость

 
Сообщений: n/a

к сожалению да =)
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Многократный поиск кратчайшего пути в графе. artem_k Графы 12 10.05.2010 13:39
Поиск самого длинного пути в ориентированном графе terlan Графы 11 26.11.2009 01:27
Поиск кратчайшего пути во взвешенном графе с заданным количеством вершин или ребер Mitrich Графы 9 24.07.2009 18:21
Поиск кратчайшего пути в бесконтурном графе гость Реализация, исходники, языки 1 06.06.2009 10:27
пути в мультиграфе незарегистрированный Графы 4 28.03.2007 09:31