Форум программистов, компьютерный форум CyberForum.ru

Оптимизация задачи о ходе шахматного коня - C++

Восстановить пароль Регистрация
 
xannn94
0 / 0 / 0
Регистрация: 17.12.2013
Сообщений: 8
24.09.2014, 16:21     Оптимизация задачи о ходе шахматного коня #1
Всем привет. В общем задача была такая:
Написать программу для следующих задач:
1.Нахождение пути шахматного коня(т.е надо чтобы конь прошёл все клетки побывав на каждой 1 раз):
2.Размерность доски должен вводить пользователь.
3.Начальные координаты коня должен вводить пользователь.
4.Программа должна реализоваться рекурсивным способом.

Полностью подходящую программу нашёл на форуме,благодаря комментариям разобрался в ней.

Теперь о проблеме:
Нужно оптимизировать программу с помощью правила Варнсдорфа при обходе доски шахматного коня следует каждый раз
ставить на то поле, из которого он может сделать наименьшее число ходов по еще не пройденным полям. Если таких полей несколько,
то можно выбрать любое из них.


(Просьба не забывать что программа обязательна должна быть рекурсивной,ну и если не сложно комментов по больше оставлять в
программе)
Вот исходник того что есть:

Кликните здесь для просмотра всего текста
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <time.h>
 
using namespace std;
 
#define move_types 8
 
int possible_moves[move_types][2]  = {
        {-1, -2}, {-2, -1}, {-2,  1}, { 1, -2},
        {-1,  2}, { 2, -1}, { 1,  2}, { 2,  1}
};
 
int **global;
int size_x, size_y;
int max_moves, back_ret;
 
 
/*Функция проверяет может ли быть сделан ход на клетку с координатами x,y*/
int move_possible(int x, int y)
{
        return x >= 0 && y >= 0 && x < size_x && y < size_y && global[x][y] == 0;
}
 
 
int find_path(int cur_x, int cur_y, int move_num)
{
        int next_x = 0, next_y = 0;
        global[cur_x][cur_y] = move_num;
 
        if(move_num > max_moves)
                return 1;
 
        for(int i = 0; i < move_types; i++)
        {       next_x = cur_x + possible_moves[i][0];
                next_y = cur_y + possible_moves[i][1];
                if(move_possible(next_x, next_y) && find_path(next_x, next_y, move_num + 1))
                return 1;
        }
 
        global[cur_x][cur_y] = 0;
        back_ret++;
        move_num++;
        return 0;
}
 
 
 
/*главная функция*/
int main()
{
setlocale (LC_ALL,"");
 
int i,nrows,ncols,sy,sx,**desc = NULL;
time_t start,end;
//вводим данные
cout<<"Введите размерность доски (от 3 до 8) :"<<endl
 <<"по оси \"X\"\t"; cin>>size_x;
cout<<"по оси \"Y\"\t";cin>>size_y;
if(size_x>8||size_x<3||size_y>8||size_y<3)
{cout<<"Неверный размер";system("pause");}
//проверяем размерность
cout<<"Введите начальные координаты:"<<endl
 <<"Координата по оси\"X\"\t";cin>>sx;
cout<<"Координата по оси\"Y\"\t";cin>>sy;
//проверяем координаты
 
 
start=time(NULL);//стартуем
//инициализируем указатель и выделяем память
desc = (int **)malloc(sizeof(int) * size_x);
for(i = 0; i < size_x; ++i)
        desc[i] = (int *)malloc(sizeof(int) * size_y);
 
//инициализируем другие переменные
back_ret = 0;
global = desc;
max_moves = size_x * size_y - 1;
 
//зануляем массив
for(int i = 0; i < size_x; ++i) {
        for(int j = 0; j < size_y; ++j)
                global[i][j] = 0;
}
 
 
//поиск решения
if(find_path(sx, sy, 1)){
 cout<<"___________________________________________"<<endl
  <<"\t***Решение***"<<endl
  <<"___________________________________________"<<endl;
 for(int i = 0; i < size_x; ++i) {
  cout<<endl;
  for(int j = 0; j < size_y; ++j)
    cout<<global[i][j]<<"\t";
    cout<<endl;}
 cout<<"___________________________________________"<<endl;
}
else cout<<"Нет решения"<<endl;
 
 
//освобождаем память
for(i = 0; i < size_x; ++i)
        free(desc[i]);
free(desc);
end=time(NULL);//время конца цикла
 
//время поиска решения
cout<<"время поиска решения "<<difftime(end, start) <<" сек."<<endl;
cout<<"___________________________________________"<<endl;
system("pause");
}


Добавлено через 6 минут
Мои мысли что делать такие: создать функцию которая записывает в массив возможные ходы(именно функцию,т.к. размер матрицы может быть разнообразен) далее перед каждым ходом делать проверку (узнать количество ходов и сортировать эти ходы(нужно выбрать ход в клетку из которой можно сделать минимальное количество ходов),после сортировки можно ходить. Как то так. Помогите реализвать всё это пожалуйста=)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.09.2014, 16:21     Оптимизация задачи о ходе шахматного коня
Посмотрите здесь:

в ходе решения задачи возникли еще вопросы ) C++
Ходы шахматного коня C++
C++ Оптимизация Кода задачи
C++ Сколько клеток находится под боем шахматного коня
C++ Найти все пути шахматного коня между двумя заданными полями, не содержащие повторяющихся полей
C++ Решение задачи на ветвление (2 коня и шахматная доска)
Ошибка в реализации задачи о ходе коня C++
Задача о ходе коня. Опять C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 09:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru