Форум программистов, компьютерный форум, киберфорум
Наши страницы

Алгоритмы

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
#1

Использование алгоритма поиска с возвратом - Алгоритмы

26.01.2013, 18:06. Просмотров 1474. Ответов 11
Метки нет (Все метки)

Добрый день, помогите пожалуйста решить проблему. Очень долго не могу составить правильную функцию для работы программы( Надо написать псевдокод для такой программы: (задача во вложении).
Я написал такой код:
STAN(min:number=0(минимальное время), temp:array[](временной массив),
diffs:array[][](таблица со временем, diffs[a][b] - время перемещения
между станциями a и b), station_index (Индекс станции), s1,s2
(пользовательское значение - станция отправки и станция прибытия));

function main():void //Главная функция
{
повторяем (i = 0; i < n; i++) //Бежим по всем станциям
{
temp.push(diffs[s1][i] + diffs[i][s2]);//Забиваем во временный массив кандидата на минимальное время
если (isMinimal(diffs[s1][i] + diffs[i][s2]))//Если оно на данном этапе действительно минимально
{
min = diffs[s1][i] + diffs[i][s2];//Забиваем как минимальное
station_index = i;//Сохраняем индекс станции
}
}
вывод (min, station_index);//Выводим время и станцию, через которую ехать
}
function isMinimal(value:Number):Boolean //Возвращет, является ли value наименьшим во временном массиве
{
повторяем ( i = 0; i < temp.length; i++)//Бежим по временному массиву
{
если (value > temp[i]) return false; //Если вдруг value больше какого-то элемента, значит оно не минимально
}
return true;
}
Проблема в том, что эта программа не учитывает того, что между станциями А и В может быть несколько связующих станций и может быть такой вариант, что такого пути нет. Для этого надо использовать поиск с возвратом, но я уже раз 5 показывал свои варианты преподу и он все отметает, говорит что ваще не то.
Ошибка начинается со строки temp.push(diffs[s1][i] + diffs[i][s2]) (нужно написать нужную функцию,но я не знаю какую) Помогите кто чем может и какие варианты можно попробовать.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.01.2013, 18:06
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Использование алгоритма поиска с возвратом (Алгоритмы):

Алгоритм поиска алгоритма - Алгоритмы
Здравствуйте! Хочу написать программу которая будет искать алгоритм который связывает числа. Тоесть допустим : 10; 20; 200; ...

Составить блок-схему алгоритма поиска всех троек натуральных чисел, удовлетворяющих условию - Алгоритмы
Составить блок-схему алгоритма следующей задачи: Дано натуральное число m. Указать все тройки натуральных чисел x, y, z ,...

Составить блок-схему алгоритма поиска частного и остатка от деления одного числа на другое - Алгоритмы
Составить блок-схему алгоритма следующей задачи: Даны натуральные числа a и b, причём b&gt;0. Найти частное и остаток при делении a на b,...

Составить блок-схему алгоритма поиска всех клеток, находящихся под ударом ферзя - Алгоритмы
Составить блок-схему алгоритма следующей задачи: Даны координаты ферзя, который находится на шахматной доске 8X8. Надо вывести массив...

Алогоритм поиска поиска покрывающего дерева (Minimal Ratio Spanning Tree) - Алгоритмы
Задача которую мне необходимо решить сводится к нахождению Minimal Ratio Spanning Tree. Условие вкратце - дан граф (связный и...

Понятие трудоёмкости алгоритма. Понятие эффективного алгоритма - Алгоритмы
Понятие трудоёмкости алгоритма. Классификация алгоритмов на основе функции трудоёмкости. Методика анализа трудоёмкости основных...

11
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
30.01.2013, 18:47  [ТС] #2
Люююди, откликнитесь кто-нибудь, пожалуйста!
0
Taatshi
Администратор
11525 / 5020 / 253
Регистрация: 05.04.2011
Сообщений: 13,759
Записей в блоге: 2
03.02.2013, 11:26 #3
Влад000, перепечатайте задание на форум.
0
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
04.02.2013, 09:22  [ТС] #4
Задание: Некоторая железнодорожная компания обслуживает n станций S1, S2, ..., Sn. Она предполагает установить информационные терминалы, с которых клиент может вводить название своей станции отправления Sa и станции назначения Sb, а ему должно выдавать расписание поездов, обеспечивающих минимальное время поездки. Написать алгоритм, который позволит это осуществить. Расписание представлено данными некоторой структуры, где перечисляется время отправления (прибытия) всех поездов (не между всеми станциями есть прямое сообщение). (Указание: использовать "поиск с возвратом")
0
Igor3D
991 / 594 / 71
Регистрация: 01.10.2012
Сообщений: 2,844
04.02.2013, 13:34 #5
Задайте сам граф, напр матрицей смежности. Напр первая строка

-1 2 -1 3

Значит из первой станции можно приехать во 2-ю за 2 часа или в 4-ю за 3 часа. А дальше просто крутите рекурсию

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void Step(
 int * path,   // пройденный путь
 int num,  // число пройденных станций
 int len )     // пройденное время 
{
 int row = path[num - 1];
 for (int i = 0; i < N; ++i) {
  if (a[row][i] <= 0) continue;
 
// проверяем след станция уже была
  int j;
  for (ij = 0; j < num; ++j)  
   if (i == path[j]) break;
  if (j < num) continue;
 
// делаем шаг
  path[num++] = i;
  len += a[row][i];
 
// нашли путь, проверяем и запоминаем если лучший (сделаете сами)
  if (i == lastStation) {
   ..
  } 
  else 
   Step(path, num, len);  // рекурс
  
// возвращаем шаг
  --num;
  len -= a[row[[i]; 
 }
}
0
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
04.02.2013, 16:44  [ТС] #6
-1 2 -1 3 - не очень понимаю, почему -1 задана станция?
0
Igor3D
991 / 594 / 71
Регистрация: 01.10.2012
Сообщений: 2,844
04.02.2013, 17:04 #7
Цитата Сообщение от Влад000 Посмотреть сообщение
-1 2 -1 3 - не очень понимаю, почему -1 задана станция?
Значит трамваи не ходют из первой в первую и из первой в третью
0
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
04.02.2013, 19:20  [ТС] #8
// нашли путь, проверяем и запоминаем если лучший (сделаете сами)
то есть создаем одномерный массив, в который будут записываться -1 2 -1 3 и прочие станции?
0
Igor3D
991 / 594 / 71
Регистрация: 01.10.2012
Сообщений: 2,844
04.02.2013, 19:35 #9
Цитата Сообщение от Влад000 Посмотреть сообщение
// нашли путь, проверяем и запоминаем если лучший (сделаете сами)
то есть создаем одномерный массив, в который будут записываться -1 2 -1 3 и прочие станции?
Нет, просто индексы станций,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
i
int bestPath[N];
int numBest = 0;
int bestLen = -1;
const int firstStation = 2;  // исходная станция (индекс)
const int lastStation = 5;  // конечная  (индекс)
 
nt main( void )
{
 int path[N];
 path[0] = firstStatin;
 Step(path, 1, 0);
 return; 
}
0
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
06.02.2013, 15:47  [ТС] #10
int j;
for (ij = 0; j < num; ++j)
if (i == path[j]) break;
if (j < num) continue;
не могу понять, почему в цикле for (ij = 0; j < num; ++j) , ij=0

Добавлено через 11 минут
i
int bestPath[N];
int numBest = 0;
int bestLen = -1;
const int firstStation = 2; // исходная станция (индекс)
const int lastStation = 5; // конечная (индекс)
и почему такие числа приравниваются? не могу понять.
0
Igor3D
991 / 594 / 71
Регистрация: 01.10.2012
Сообщений: 2,844
06.02.2013, 16:28 #11
Цитата Сообщение от Влад000 Посмотреть сообщение
int j;
и почему такие числа приравниваются? не могу понять.
Если есть "станции", Вы так или иначе храните их в виде массива (в общем случае контейнера). Как Вы зададите станцию с которой начинаете? Индексом (порядковым номером) в массиве. Как Вы напечатаете найденный маршрут? Массивом индексов, напр {2, 0, 1, 5}

Влад, что-то совсем мрачно - видать гульки на уме а не программирование Больше на вопросы типа "ничего не понимаю" отвечать не буду
0
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
06.02.2013, 18:15  [ТС] #12
Спасибо. Просто я задачу саму понять не мог в плане того, как должен выглядеть конечный ответ.

Добавлено через 1 минуту
В общем вот:
Код
STEP(*path (пройденный путь), num (число пройденных станций),
len (пройденное время))
{
 row = path[num-1];
  for (i = 0; i < N; i++)
{
 if (a[row][i]<= 0) continue;
// проверяем след станция уже была
  j;
  for (ij = 0; j<num; ++j)
  if (i == path[j]) break;
  if (j < num) continue;
// делаем шаг
path[num++] = i;
len += a[row][i];
// нашли путь, проверяем и запоминаем, если лучший
  if (i == lastStation) {
   int bestPath[N];
int numBest = 0;
int bestLen = -1;
const int firstStation = 2;  // исходная станция (индекс)
const int lastStation = 5;  // конечная  (индекс)
 
nt main( void )
{
 int path[N];
 path[0] = firstStatin;
 Step(path, 1, 0);
 return; 
}
  } 
  else 
   Step(path, num, len);  // рекурс
  
// возвращаем шаг
  --num;
  len -= a[row[[i]; 
 }
}
все так?
0
06.02.2013, 18:15
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.02.2013, 18:15
Привет! Вот еще темы с ответами:

Пояснить суть алгоритма поиска с возвратом - Turbo Pascal
Здравствуйте) Ни как не могу понять &quot;смысл&quot; алгоритма с возвратом... :( Какая у него функция? может кто подскажет...

Реализуйте на практике 2 алгоритма поиска и 2 алгоритма сортировки. Результаты сравните - C++ Linux
Всем привет! Я в С++ абсолютный чайнег, поэтому за дебильные вопросы сапогами не пинайте))) в общем есть код работающий в борланде....

.NET 4.x Использование хранимой процедуры с возвратом состояния - C#
Добрый день. Не могу понять как считывать состояние процедуры. ALTER PROCEDURE . @login nchar(20), @pass nchar(15) AS BEGIN if...

Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом. - C++
Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом. Общий алгоритм хотя бы. Ну а лучше всю прогу...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru