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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 01.03.2011, 12:02
Новичок

Отправить личное сообщение для babas1983 Посмотреть профиль Найти все сообщения от babas1983
 
Регистрация: 28.02.2011
Сообщений: 3

Нужен граф.
Здравствуйте!
Начал осваивать С++ - мои достижения на сверхминимальном уровне.
Задал координаты вершин и матрицу смежности графа. Для наглядности нарисовал себе граф на листке бумаги )) Длину ребер программк вычисляет по Пифагору, используя координаты.
Моя цель - реализовать и проанализировать работу алгоритма поиска кратчайшего пути (А*).
Я задал граф из 34 вершин - это не бычтро ручками делать.

ПРОСЬБА - поделиться графом большой размерности.
И объяснить как мне его в мое элементарное консольное приложение подставить - если граф задан отличным от моего способом.
Мой ящик: babas1983@list.ru

Заранее всем спасибо!!!
  #2  
Старый 01.03.2011, 13:46
гocть

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

A* говорите? ну попробуй например http://en.wikipedia.org/wiki/Fifteen_puzzle -
там граф размер 16 факториал - достаточно большой?

или то же самое но размера 3x3 - тогда 9! состояний, есть 15! вдруг слишком много. вот тут можешь провериться - http://acm.uva.es/p/v6/652.html
  #3  
Старый 01.03.2011, 14:33
Новичок

Отправить личное сообщение для babas1983 Посмотреть профиль Найти все сообщения от babas1983
 
Регистрация: 28.02.2011
Сообщений: 3

Спасибо )
Игра в ПЯТНАШКИ расписана в литературе.
Я пробую А* не на пространстве (ребра все одинаковы), а на графе, приближенном к реальной дорожной сети! Здесь А* часто не справляется - пытается "идти на прямую", а это далеко от кратчайшего пути, найденного по Дийкстре. Пытаюсь модифицировать алгоритм. А для экспериментов, нужен граф, желательно большой, но чтоб я его мог визуализировать и "наглядно" отслеживать работу алгоритма!
  #4  
Старый 02.03.2011, 01:22
гocть

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

Есть публично доступные карты от проекта OpenStreetMap, дороги там есть. Возможно, прилично (или неприлично) повозившись, можно достать граф из их данных, стартовая точка - http://wiki.openstreetmap.org/wiki/Routing

Есть граф дорог Москвы от Яндекса - http://imat2010.yandex.ru/datasets - то там, по моему, без координат (коммерческая тайна), так что тебе для A* возможно не подойдет.
  #5  
Старый 02.03.2011, 01:41
Новичок

Отправить личное сообщение для babas1983 Посмотреть профиль Найти все сообщения от babas1983
 
Регистрация: 28.02.2011
Сообщений: 3

Спасибо
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача. Граф и т.д. useroto Задачи 1 25.12.2010 17:41
Граф tewi Реализация, исходники, языки 5 01.11.2010 15:47
Как красиво нарисовать граф? Selmaril Графы 2 08.10.2010 22:45
Платоновый граф helm Графы 3 25.12.2009 01:02
граф в win32 гость Графы 11 08.04.2009 03:07