Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 24.04.2009, 11:31
Новичок на форуме
Отправить личное сообщение для IVIbILLIb Посмотреть профиль Найти все сообщения от IVIbILLIb
 
Регистрация: 24.04.2009
Сообщений: 2

Поиск кротчайшего пути
помогите написать на javascript код нахождения пути условия карта прямоугольная разбитая на квадраты количество квадратов по линии х и по линии y известно попадаються непроходимые участки пожно переходить с одной клетки на другую как по диагонали, вертикали и горизонтали время перехода различно и закреплено за каждой клеткой (переход из клетки в соседнии по времени одинаково а уже переход из соседней клетки в другие будет отличаться) помогите кодом плз с описанием я пока новичек
Ответить с цитированием
  #2 (permalink)  
Старый 24.04.2009, 11:52
Новичок на форуме
Отправить личное сообщение для Kolyaj Посмотреть профиль Найти все сообщения от Kolyaj
 
Регистрация: 19.02.2008
Сообщений: 9,177

А теперь то же самое, но со знаками препинания. Их не просто так в школе проходят. Это читать невозможно.
Ответить с цитированием
  #3 (permalink)  
Старый 24.04.2009, 16:55
Аватар для Gvozd
Матрос
Отправить личное сообщение для Gvozd Посмотреть профиль Найти все сообщения от Gvozd
 
Регистрация: 04.04.2008
Сообщений: 6,245

+1 к вопросу о знаках препинания.
но кажется я догадался что вам надо.
Это класическая алгоритмическая задача, рассмотренная неймоверное количество раз практически на всех живых языках, и рискну предположить на некоторых эзотерических.
Как вывод:
1)Ищите лучше.В сети уже есть решение, навреняка и на JS
2)Есть куча книг по алгоритмам, где есть описание решения этой задачи на словах, и как правило на одном-двух языках програмирования.
Как правило этого вполне достаточно, чтобы написать реализацию на своем языке.

Сам алгоритм вашей задачи решается класически с помощью рекурсии.
рекурсивно обходите все возможные пути, на каждой итерации рекурсии, совершая переходы из текущей ячейки во все соседние, доступные(даже если это шаг "назад").
Учитывая специфику задачи, для избежания зацикливания, запоминайте пройденный путь, и на клетки из него не идите.
в глобальной области видимости держите массив, куда будете записывать самый короткий путь, и переменную, для его длины.
по достижении цели, перезаписывайте их, если новый путь короче.
По окончании рекурсивной функции, у вас на руках будет путь, и его длина.Этот путь и будет одним из кратчайших(может быть несколько одинаковых по длине кратчайших)

Если вы не в состоянии оформить эту мысль в код JS, то идите и учите теорию JS.При необходимости и алгоритмизацию. Готового решения от скуки, за просто так вам тут не разместят.

Удачного кодинга!
Ответить с цитированием
  #4 (permalink)  
Старый 24.04.2009, 16:58
Новичок на форуме
Отправить личное сообщение для Kolyaj Посмотреть профиль Найти все сообщения от Kolyaj
 
Регистрация: 19.02.2008
Сообщений: 9,177

Ключевые слова: волновой алгоритм.
Ответить с цитированием
  #5 (permalink)  
Старый 28.04.2009, 08:10
Новичок на форуме
Отправить личное сообщение для IVIbILLIb Посмотреть профиль Найти все сообщения от IVIbILLIb
 
Регистрация: 24.04.2009
Сообщений: 2

Волновой алгоритм ищет только минимальное количество вершин от точки А до точки Б. Мне же необходимо кратчайшее растояние. Сеть уже обшарил и нашел решения на С++, Delphi и Паскале, но они находят не кратчайший путь а просто путь от точки к точке при этом путь является не только не кратчайшим, но и не минимальным по количеству ребер.
И если у вас нет кода то подскажите просто как это можно оформить без цикла, просто карта обьемная и через циклы скрипт прогружается очень долго!
Ответить с цитированием
  #6 (permalink)  
Старый 28.04.2009, 09:08
Новичок на форуме
Отправить личное сообщение для Kolyaj Посмотреть профиль Найти все сообщения от Kolyaj
 
Регистрация: 19.02.2008
Сообщений: 9,177

Количество вершин -- частный случай расстояния, если вес каждого ребра равен 1. Что мешает на каждом шаге прибавлять не единицу, а вес ребра?
Ответить с цитированием
  #7 (permalink)  
Старый 02.05.2009, 17:11
Аспирант
Отправить личное сообщение для milk3dfx Посмотреть профиль Найти все сообщения от milk3dfx
 
Регистрация: 26.01.2009
Сообщений: 30

Цитата:
карта обьемная
Если не секрет, для каких целей вам нужен алгоритм? Для 3D игры?
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск в строке другой подстроки средствами JS YAN Общие вопросы Javascript 13 23.07.2013 09:41
Поиск на странице no_name jQuery 4 07.09.2010 13:26
Для чего ограничен поиск? ZoNT Сайт Javascript.ru 4 01.10.2008 15:55
Поиск в массиве через JavaScript Noran Общие вопросы Javascript 0 10.08.2008 17:31
Поиск текста и замена krestiyaninov Общие вопросы Javascript 1 07.05.2008 13:30