The two basic elements of a rule-based expert system shell are a knowledge base
ID: 648569 • Letter: T
Question
The two basic elements of a rule-based expert system shell are a knowledge base and an inference engine. The knowledge base contains the domain knowledge in the form of rules. The inference engine uses these rules to produce a solution to a given problem.
The inference engine operates in cycles. In each cycle, it first determines which rules can be activated for firing (called activated rules), then selects one rule for execution and finally executes the selected rule. Each activated rule has a corresponding priority. An agenda contains a list of activated rules, with their priorities, maintained by an agenda manager. In each cycle, an agenda manager updates list of activated rules by adding new activated rules and deleting rules that are no longer activated and the rule that was executed in a previous cycle.
You are to implement a simplified agenda manager. In each cycle, the agenda manager first deletes from the agenda the activated rule that was executed in a previous cycle. A list of new activated rules is given to the agenda manager to add to the agenda. Once a rule is added to the agenda, it remains there until it is executed. An agenda manager then determines the rule with highest priority for the inference engine to execute in this cycle. Only one rule can be executed in each cycle. A rule that has been executed and removed from the agenda may be put on the agenda again in the next cycle. The system halts when the agenda is empty or after it runs 30 cycles.
Your implementation must use a priority queue implemented by using a heap. For simplicity, assume that the agenda can contain at most 300 rules (although a system may have more than 300 rules). Each rule is represented by a character string of length 5 and a priority of range between 1 and 100.
The agenda manager takes a file named input.txt as input. Each line of the file is a list of ordered pairs (x, y) where x is a rule and y is a priority. The agenda manager builds a priority queue (heap) from the rules and priorities in the first line of the file. It then outputs the rule with the highest priority and removes it from the queue. Each subsequent line of the input file is used as the list of rules to be added in another cycle.
Example of input file:
(arule, 12), (brule, 21), (zrule, 70), (drule, 25), (erule, 10) (frule, 3)
(grule, 20), (srule, 100)
The actions of the agenda manager for this file are:
Cycle 1: Build a priority queue (heap) containing the 5 rules with corresponding priorities as in
line 1. Output zrule and remove it from the queue.
Cycle 2: Add frule with priority 3 to queue. Output drule and remove it from the queue.
Cycle 3: Add grule and srule with respective priorities 20 and 100 to the queue. Output srule
and remove it from the queue.
Cycles 4-8: Output and remove from the queue rules brule, grule, arule, erule, and frule.
Your agenda manager must include the following operations:
BuildQueue: builds a priority queue (heap) from an unsorted array of rules with priorities Heapify: used by BuildQueue to maintain the heap properly
ExtractMax: returns the rule with the highest priority
Insert: adds a new rule to the queue
Delete: removes a rule from the queue
What to submit:
Part 1: Results obtained from the runs against each of the given tests. The results should show
content of the agenda in each reasoning cycle and clearly state which cycle the inference
terminates.
Part 2: Intelligent and concise documentation.
Part 3: (bonus 10%) Experiment to see the run time performance of your simplified agenda
manager for different problem sizes. Show the graph of the above result and relate it to the asymptotic behavior of the worst case run time.
Explanation / Answer
Program:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>
int extractmax(int *);
void insert(int *,int );
void heapify(int *,int );
int hsize;
struct heap
{
char *rule;
int *priority
}*h;
void main()
{
int size,n;
char name[10];
int res,ch=1,i;
clrscr();
h=((struct heap*)malloc(sizeof(struct heap));
int n, i, temp, ch, val;
FILE *file;
file=fopen("input.txt","r")
i=0;
while(!file)
{
fscanf(file,"%s",heap->data[i]);
fscanf(file,"%s",heap->priority[i]);
i++;
}
buildQueue(h,i);
hsize=0;
do
{
printf(" 1.Insert an element");
printf(" 2.Maximum Element");
printf(" 3.Exit ");
printf(" Enter your option :");
scanf("%d",&option);
switch(option)
{
case 1:
printf(" Enter the rule:");
scanf("%s",name);
printf(" Enter element");
scanf("%d",&n);
insert(h,name,n);
break;
case 2:
name=extractmax(a);
printf(" The Rule which has the higehest Priority is");
printf("%s,name);
break;
case 3:
break;
case 4:
exit(0);
}
printf(" Do you want to do the opeartions once again(1/2)?");
scanf("%d",&ch);
}while(ch==1);
getch();
}
void buildQueue(struct heap *h, int index) {
int val = h->priority[index];
char name1[10]=h->rule[index];
while (h->priority[(index - 1) / 2] >= val) {
h->priority[index] = h->priority[(index - 1) / 2];
h->rule[index] = h->rule[(index - 1) / 2];
if (!index)
break;
index = (index - 1) / 2;
}
h->priority[index] = val;
h->rule[index]=name1;
return;
}
void heapmax(struct heap *h)
{
if(hsize<1)
{
printf(" No rule in the queue");
exit(1);
}
printf(" The priority of the rule which has the highest priority %d",h->priority[0]);
}
char *extractmax(struct heap *h)
{
char name;
if(hsize<1)
{
printf(" No element in the queue");
return 0;
}
name=h->rule[0];
h->rule[0]=h->rule[hsize-1];
hsize=hize-1;
heapify(h,0);
return name;
}
void heapincreasekey(struct heap *h,int i,char name[10],int key)
{
int parent,temp;
char name1[10];
h->priority[i]=key;
while(i>0)
{
parent=(i-1)/2;
if(h->priority[i]>h->priority[parent])
{
temp=h->priority[i];
h->priority[i]=h->prirority[parent];
h->priority[parent]=temp;
name1=h->rule[i];
h->rule[i]=h->rule[parent];
h->rule[parent]=name1;
}
i=parent;
}
}
void insert(struct heap *h,char name[10],int key)
{
a[hsize]=-1;
hsize=hsize+1;
heapincreasekey(h,hsize-1,name,key);
}
void heapify(struct heap *h,int i)
{
int left,right,large,temp;
char name1[10];
left=2*i+1;
right=2*i+2;
if(left<hsize && h->priority[i]<priority[left])
large=left;
else
large=i;
if(right<hsize && h->priority[right]>h->priority[large])
large=right;
if(large!=i)
{
temp=h->priority[i];
h->priority[i]=h->priority[large];
h->priority[large]=temp;
name1=h->rule[i];
h->rule[i]=h->rule[large];
h->rule[large]=name1;
heapify(h,large);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.