Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритм бектрекінг
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2017
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Методи і системи штучного інтелекту
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІСЬКА ПОЛІТЕХНІКА»
Кафедра ІСМ
Звіт
До лабораторної роботи №4
З дисципліни:
«Методи та системи штучного інтелекту»
На тему:
«Алгоритм бектрекінг»
Львів-2017
Мета роботи: полягає у вивченні алгоритмів бектрекінг та його застосування при розв’язуванні задач штучного інтелекту.
Теоретичні відомості
Опишемо загальний метод, який дозволяє значно зменшити об’єм обчислень в алгоритмах типу „повного перебору всіх можливостей”. Щоб застосувати цей метод, розв’язок задачі повинен мати вигляд послідовності (x x) n , ..., 1 . Основна ідея методу полягає в тому, що розв’язок будується поступово, починаючи з порожньої послідовності (довжини 0), або з одноелементної послідовності (довжини 1). Взагалі, якщо маємо даний частковий (неповний) розв’язок ( ) i x , , x 1.. , де i<n , то намагаємось знайти таке допустиме значення i+1 x , що не включається можливість продовження ( ) 1 1 , , , i i x x x ( ) до повного розв’язку. Якщо такого значення i+1 x не існує, то повертаємось до попередньої послідовності ( ) 1 1 , I x x і продовжуємо процес, шукаючи нове, ще не використане значення xi ( ) звідси назва „бектрекінг” (англ. backtracking – пошук з поверненням). Роботу цього алгоритму можна інтерпретувати як процес обходу деякого дерева. Кожна вершина цього дерева природно відповідає деякій послідовності ( ) i x , , x 1, причому вершини, які відповідають послідовностям виду (x x y) i , , , 1 .. , є синами цієї вершини. Корінь дерева відповідає порожній, а в деяких задачах одноелементній послідовності. В алгоритмі бектрекінг здійснюється обхід цього дерева пошуком вглиб (для дерева це означає обхід зверху вниз). Крім того, задається предикат P , означений на всіх вершинах дерева. У випадку P (v) =F процес обходу відкидає розгляд вершин піддерева з коренем у вершині v , зменшуючи тим самим обсяг перебору.
Завдання лабораторної роботи:
Знайти підмножину цієї множини таку, що сума її елементів дорівнює даному числу M ( k =1).
Результати виконання роботи:
package PHSHI.Lab4;
import java.util.ArrayList;
import java.util.Scanner;
public class Lab4 {
public static void main(String[] args) {
System.out.println("Введіть кількість елементів множини:");
Scanner scanner = new Scanner(System.in);
int count = scanner.nextInt();
System.out.println("Введіть " + count + " елементів множини");
int matrix[] = new int[count];
for (int i = 0; i < count; i++) {
matrix[i] = scanner.nextInt();
}
ArrayList<Integer> list = new ArrayList<Integer>();
ArrayList<String> list2 = new ArrayList<String>();
list2.add("a");
System.out.println("Введіть М:");
int M = scanner.nextInt();
int sum = 0, count2 = 0;
int f = fact(count);
int i = 0;
int count3 = 0;
m1:
while (sum != M && count2 < f) {
if (i < count) {
if (!list.contains(matrix[i])) if (!contain(list2, list.toString())) {
sum += matrix[i];
if (sum == M) {
list.add(matrix[i]);
break m1;
}
if (sum < M) {
list.add(matrix[i]);
i++;
count3 = i;
} else {
sum -= matrix[i];
count3++;
i++;
}
if (count3 >= count && list.size() > 0) {
// System.out.println(list.toString());
list2.add(list.toString());
sum -= list.get(list.size() - 1);
list.remove(list.size() - 1);
i = 0;
count3 = 0;
}
} else {
sum -= matrix[--i];
if (list.size() > 0) list.remove(list.indexOf(matrix[i]));
i++;
count3 = list.size();
// System.out.println("List: "+list);
}
else i++;
} else if (i > 1) i = 0;
count2++;
System.out.println(list + " " + sum);
}
System.out.println("Winner: " + list);
}
static int fact(int count) {
if (count == 1) return 1;
else return fact(count - 1) * count;
}
static boolean contain(ArrayList<String> list2, String list) {
for (int i = 0; i < list2.size(); i++)
if (list2.get(i).equals(list)) {
// System.out.println(list2.get(i) + " " + list);
return true;
}
return false;
}
}
В даній програмі використовувався текстовий інтерфейс. Нам спершу необхідно ввести деякі елементи множини, щоб надалі виконати умови поставленого завдання.
/ Рис. 1. Результати виконання роботи
Висновок
Виконавши дану лабораторну роботу, вивчила алгоритми бектрекінгу та його застосування при розв’язуванні задач штучного інтелекту.
30.05.2019 15:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора