Тестирование программы
В результате тестирования программы ни одной ошибки, мешающей работе программы, обнаружено не было. Программа работает при любых заданных условиях. В результате решения задачи данной для тестирования программы, было найдено решение этой задачи, ответ которой полностью совпал с ответом, найденным разработчиком самостоятельно. Программа полностью готова к работе, независимо от того, будет ли пользователь следовать инструкции по использованию программы или нет.
У данной программы есть только один недостаток – если при решении задачи могут иметься несколько вариантов решений, то программа будет рассматривать только одно, так что пользователю будет выведена информация только об одном решении.
3.7 Инструкция пользователю
После того как пользователь запустил исполняемый файл, на рабочем столе появится пустое окно (рис В1), в котором пользователь должен ввести цифру количества столбцов и строк таблицы. Число строк соответствует числу городов. Так как созданная таблица будет квадратная , то пользователю достаточно ввести одну цифру.
Далее открывается окно с созданной таблицей (рис. В2), в которую следует ввести цифры из таблицы, данной в качестве условия пользователю. Цифры соответствуют расстояниям между городами. В данном окне так же возможен выбор города, с которого коммивояжер начнет маршрут.
После того, как все поля таблицы заполнены, следует нажать кнопку «Продолжить»
В третьем окне появится результат подсчетов программы, а именно оптимальный маршрут между данными городами и расстояние, потраченное на прохождение этого маршрута.(рис.В3)
Заключение
В данном курсовом проекте был рассмотрен вопрос о создании программы для решения задачи «коммивояжёра» прямым алгоритмом.
Суть прямого алгоритма в следующем: Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:
- маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;
- в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.
Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого. Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.
Для того, чтобы начать решать задачу необходимы условия задачи, в данном случае они представлены в виде таблицы 1. В таблице даны расстояния между городов.
В результате решения задачи самым оптимальным маршрутом между данными городами был выявлен маршрут, состоящий из семи шагов, а именно:
1->5->4->3->6->7->2->1.
Длинна пройденного пути для этого маршрута оказалась самой наименьшей:
Q = 22
Ответ совпал с ответом задачи, решенной программистом, значит программа написана верно.
Далее была создана инструкция для пользователей, где программа была полностью расписана.
После того как пользователь запустил исполняемый файл, на рабочем столе появится пустое окно (рис В1), в котором пользователь должен ввести цифру количества столбцов и строк таблицы. Число строк соответствует числу городов. Так как созданная таблица будет квадратная , то пользователю достаточно ввести одну цифру.
Далее открывается окно с созданной таблицей (рис. В2), в которую следует ввести цифры из таблицы, данной в качестве условия пользователю. Цифры соответствуют расстояниям между городами. В данном окне так же возможен выбор города, с которого коммивояжер начнет маршрут.
После того, как все поля таблицы заполнены, следует нажать кнопку «Продолжить»
В третьем окне появится результат подсчетов программы, а именно оптимальный маршрут между данными городами и расстояние, потраченное на прохождение этого маршрута.(рис.В3)
Подведем итог, после всех перечисленных шагов, получилась программа, позволяющая высчитать ответ, согласно решению задач «коммивояжера» все пункты были детально рассмотрены и выполнены, благодаря этому цель курсового проекта была достигнута.
Приложение А. Глоссарий понятий
Задачи коммивояжера.
Прямой алгоритм.
Метод ветвей и границ.
Маршрут.
Форма.
Шаги.
Модуль программы.
Нелинейное программирование.
Таблица.
Функции.
Экономическая постановка задачи.
Математическая постановка задачи.
Блок - схема.
Приложение Б. Текст программы
Форма 1.
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace ex_20
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
int x;
int[,] matrix;
int[,] new_matrix;
int start;
int[] second;
int q;
string _q;
string _l;
bool[] vis;
int count;
int j_min;
private void Form1_Load(object sender, EventArgs e)
{
Form2 f2 = new Form2();
f2.ShowDialog();
if (!f2.error)
{
x = f2.getResult();
f2.Dispose();
Form3 f3 = new Form3(x);
f3.ShowDialog();
if (!f3.error)
{
Class1 gr = f3.getResultate();
f3.Dispose();
x = gr.x;
matrix = gr.matrix;
start = gr.start;
string starting = (start + 1).ToString();
vis = new bool[x];
second = new int[x * x];
new_matrix = new int[x, x];
count = 0;
for (int j = 0; j < x * x; j++)
{
for (int i = 0; i < x; i++)
if (i != start && !vis[i])
{
second[count] = matrix[start, i];
j_min = i;
}
if (second[count] != 0)
{
for (int i = 0; i < x; i++)
if (i != start && matrix[start, i] < second[count] && !vis[i])
{
second[count] = matrix[start, i];
j_min = i;
}
if (count == 0)
{
_q = second[count].ToString();
_l = (start + 1).ToString();
}
else
{
_q += string.Format(" + {0}", second[count]);
_l += string.Format(" -> {0}", start + 1);
}
q += second[count];
new_matrix[start, j_min] = second[count];
vis[start] = true;
start = j_min;
vis[j_min] = true;
count++;
}
else
break;
}
_l += string.Format(" -> {0} -> {1}", start + 1, starting);
_q += string.Format(" + {0}", matrix[start, Convert.ToInt16(starting) - 1]);
q += matrix[start, Convert.ToInt16(starting) - 1];
new_matrix[start, Convert.ToInt16(starting) - 1] = matrix[start, Convert.ToInt16(starting) - 1];
label1.Text = string.Format("Q = {0} = {1} L = {2}", _q, q, _l);
int loc_x = 12;
int loc_y = 53;
int l_y = 0;
int l_x = 0;
Label[,] lbl = new Label[x,x];
for (int i = 0; i < x; i++)
{
l_y = loc_y * (i + 1);
Label lb = new Label();
lb.Size = new Size(50, 15);
lb.AutoSize = false;
lb.Text = string.Format("Город {0}", i + 1);
lb.Location = new Point(14, l_y);
this.Controls.Add(lb);
for (int j = 0; j < x; j++)
{
l_x = (loc_x + 50) * (j + 1);
if (j == 0)
{
int lo_x = (loc_x + 50) * (i + 1);
Label lab = new Label();
lab.Size = new Size(50, 15);
lab.AutoSize = false;
lab.Text = string.Format("Город {0}", i + 1);
lab.Location = new Point(lo_x, 30);
this.Controls.Add(lab);
}
if (i != j && new_matrix[i, j] != 0)
{
lbl[i, j] = new Label();
lbl[i, j].Text = new_matrix[i, j].ToString();
lbl[i, j].Size = new Size(40, 20);
lbl[i, j].Location = new Point(l_x + 15, l_y);
this.Controls.Add(lbl[i, j]);
}
}
}
return;
}
}
this.Close();
}
}
}
Форма 2.
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace ex_20
{
public partial class Form2 : Form
{
public Form2()
{
InitializeComponent();
button1.Enabled = false;
}
int x = 0;
public bool error = true;
private void button1_Click(object sender, EventArgs e)
{
error = false;
try { x = Convert.ToInt16(textBox1.Text); }
catch
{
MessageBox.Show("Значение введено не верно !");
error = true;
return;
}
if (x < 3)
{
MessageBox.Show("Значение введено не верно !");
error = true;
return;
}
this.Close();
}
private void textBox1_TextChanged(object sender, EventArgs e)
{
if (textBox1.Text.Length != 0)
button1.Enabled = true;
else
button1.Enabled = false;
}
public int getResult() { return x; }
}
}
Форма 3.
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace ex_20
{
public partial class Form3 : Form
{
int x = 0;
TextBox[,] tb;
int[,] matrix;
public Form3(int x)
{
InitializeComponent();
this.x = x;
tb = new TextBox[x, x];
int loc_x = 12;
int loc_y = 53;
int l_y = 0;
int l_x = 0;
for (int i = 0; i < x; i++)
{
l_y = loc_y * (i + 1);
Label lb = new Label();
lb.Size = new Size(50, 15);
lb.AutoSize = false;
lb.Text = string.Format("Город {0}", i + 1);
comboBox1.Items.Add(i + 1);
lb.Location = new Point(14, l_y + 4);
this.Controls.Add(lb);
for (int j = 0; j < x; j++)
{
l_x = (loc_x + 50) * (j + 1);
if (j == 0)
{
int lo_x = (loc_x + 50) * (i + 1);
Label lab = new Label();
lab.Size = new Size(50, 15);
lab.AutoSize = false;
lab.Text = string.Format("Город {0}", i + 1);
lab.Location = new Point(lo_x, 37);
this.Controls.Add(lab);
}
tb[i, j] = new TextBox();
if (i == j)
{
tb[i, j].Text = "∞";
tb[i, j].TextAlign = HorizontalAlignment.Center;
tb[i, j].Enabled = false;
tb[i, j].Font = new System.Drawing.Font("Microsoft Sans Serif", 11F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(204)));
}
tb[i, j].Size = new Size(40, 20);
tb[i, j].Location = new Point(l_x, l_y);
this.Controls.Add(tb[i, j]);
}
}
comboBox1.SelectedIndex = 0;
}
public bool error = true;
private void button1_Click(object sender, EventArgs e)
{
error = false;
matrix = new int[x, x];
for(int i = 0; i < x; i++)
for (int j = 0; j < x; j++)
{
if(i != j)
try { matrix[i, j] = Convert.ToInt16(tb[i, j].Text); }
catch { error = true; }
}
if (error)
{
MessageBox.Show("Значения введены не верно !");
return;
}
this.Close();
}
public Class1 getResultate() { Class1 gr = new Class1(x, matrix, comboBox1.SelectedIndex); return gr; }
}
}
Приложение В. Видовые экраны работы программы
Рис. В1 Форма 1
Рис. В2 Форма 2
Рис. В3 Форма 3
Приложение Г. Алгоритм решения задачи