نرمز نظرياً لثخانة البيان G ب( Φ(G وتعرف ثخانة البيان بأنها العدد الأصغري من البيانات الجزئية المسطحة(المستوية ) والتي نستطيع الحصول عليها من تحميل البيان الأصلي G والبيان المسطح هو كل بيان يمكن إعادة رسمه في المستوي بدون أن تتقاطع أضلاعه (خطوط التوصيّل بين الر ؤوس)، لذلك عرفت مسألة تحديد ثخانة البيان كمسألة تنتمي إلى صف المسائل
.NP-complete
سنقدم في هذا البحث تطبيقاً لخوارزمية تجريبية Heuristic Algorithm تعتمد على مفهوم محاكاة تلدين الفلزات الأمثلScheme Simulated Annealing Optimization
New- hick الذي يساعد في تحسين نتائج الخوارزمية التجريبية المقترحة
حيث أعطى حلاً فعالاً وسريعاً في إيجاد ثخانة البيانات التامة والثنائية التامة
عندما يكون عدد رؤوس البيان n<=30 وأبطأ عندما يكون أكبر من ذلك.
أخيرا نعرض نتائج تطبيق هذه الخوارزمية على الخوارزمية التجريبية
فنلاحظ بأنها أعطت حلاً أمثلياً لتحديد ثخانة البيانات التامة والثنائية التامة. كما تمّت برمجة هذه الخوارزمية باستخدام لغة عالية المستوى ++C بمفهوم غرضي التوجه وقد حصلنا على النتائج بتنفيذ البرنامج على حاسوب بمواصفات RAM 2GB, CPU, M350 2.27GHZ
The graph-theoretical thickness (shortly thickness)of graph G,
denoted by Φ(G), is the minimum number of planar subgraphs into
which the graph can be decomposed, and a graph that can be
drawn in the plane without any of its edges intersecting is called a
planar graph. determining the thickness of a given graph is known
to be an NP-complete problem.
In this paper we introduce an application heuristic algorithm for
determining the thickness. Our algorithm is based on simulated
annealing optimization scheme which provide the results of the
New-thick (1). We show that the simulated annealing is a efficient
method to obtain good approximation for the thickness when the
number vertices are at most 30 otherwise it is slower.
Finally, we apply this algorithm on the heuristic algorithm Newthick
and we show that the algorithm produces a good
approximation and optimization solution for the thickness, and we
program this algorithm with C++, and running it by laptop has
RAM 2GB and CPU 2.27GHZ.
Artificial intelligence review:
Research summary
تتناول هذه الورقة البحثية مسألة تحديد تخانة البيانات التامة والثنائية التامة، وهي مسألة تنتمي إلى صف المسائل NP-complete. تقدم الورقة خوارزمية تجريبية تعتمد على مفهوم محاكاة تلدين الفلزات الأمثل (Simulated Annealing Optimization) لتحسين نتائج الخوارزمية المقترحة New-thick. تُظهر النتائج أن الخوارزمية المقترحة فعالة وسريعة عندما يكون عدد رؤوس البيان أقل من أو يساوي 30، لكنها تصبح أبطأ عندما يزيد العدد عن ذلك. تم برمجة الخوارزمية باستخدام لغة ++C وتم تنفيذها على حاسوب بمواصفات RAM 2GB و CPU 2.27GHz. تُظهر النتائج أن الخوارزمية الجديدة تعطي حلاً أمثلياً لتحديد تخانة البيانات التامة والثنائية التامة مقارنة بالخوارزميات السابقة.
Critical review
دراسة نقدية: تقدم الورقة البحثية حلاً مبتكراً لمشكلة معقدة في نظرية البيانات، ولكن هناك بعض النقاط التي يمكن تحسينها. أولاً، على الرغم من أن الخوارزمية فعالة لرؤوس البيانات التي لا تتجاوز 30، إلا أنها تصبح أبطأ مع زيادة عدد الرؤوس، مما يحد من تطبيقها على البيانات الكبيرة. ثانياً، لم يتم تقديم تحليل تفصيلي لكيفية تأثير بارامترات التبريد والتجميد على أداء الخوارزمية، وهو أمر مهم لفهم كيفية تحسين الخوارزمية بشكل أكبر. أخيراً، قد يكون من المفيد تقديم مقارنة أكثر تفصيلاً مع خوارزميات أخرى مشابهة لتحديد مدى تفوق الخوارزمية المقترحة.
Questions related to the research
-
ما هي الخوارزمية المقترحة في هذه الورقة لتحديد تخانة البيانات التامة والثنائية التامة؟
الخوارزمية المقترحة هي New-thick، والتي تعتمد على مفهوم محاكاة تلدين الفلزات الأمثل لتحسين نتائج الخوارزمية التجريبية.
-
ما هي مشكلة تحديد تخانة البيانات ولماذا تعتبر معقدة؟
تحديد تخانة البيانات هو عملية تقسيم البيان إلى أقل عدد ممكن من البيانات الجزئية المسطحة. تعتبر هذه المشكلة معقدة لأنها تنتمي إلى صف المسائل NP-complete، مما يعني أنه لا يوجد حل بزمن كثيرة حدود معروف لها.
-
ما هي نتائج تطبيق الخوارزمية المقترحة على البيانات التامة والثنائية التامة؟
أظهرت النتائج أن الخوارزمية المقترحة تعطي حلاً أمثلياً لتحديد تخانة البيانات التامة والثنائية التامة عندما يكون عدد رؤوس البيان أقل من أو يساوي 30، لكنها تصبح أبطأ عندما يزيد العدد عن ذلك.
-
ما هي اللغة البرمجية المستخدمة في برمجة الخوارزمية وما هي مواصفات الحاسوب المستخدم لتنفيذها؟
تم برمجة الخوارزمية باستخدام لغة ++C وتم تنفيذها على حاسوب بمواصفات RAM 2GB و CPU 2.27GHz.
References used
BONDY, J and MURTY, U. S 2008-Graph Theory . Springer
artrand,G 1993-Applied and Algorithmic Graph Theory. McGraw-Hill,Inc, International Edition United States of America, 395
Daniel Liang,Y 2010-Introduction to Programming With C++. Pearson Education International, second edition United States of America, 694
Eles, P 2010- Simulated Annealing.Department of Computer and Information Science (IDA)Linköpings Universitet
JOHN,M. MICHAEL,J and JEFFRY,L 2008-Combinatorics and Graph Theory, second edition Springer, 392
The aim of this paper is to study and generalize some results that related by the complete continuity of the urysohn.s operator of two variables on a set on which a lebesgue meagure is defined and study uniform convergence sequence of the urysohn .s.
In spite of the significant progress in surgery , the "best" surgical technique for
the management of complete rectal prolapse remains controversial, due to its low incidence, which is the
cause that there are no large prospective randomized trials
As it’s known, The Graph k-Colorability Problem (GCP) is a wellknown
NP-Hard Problem. This problem consists in finding the k
minimum number of colors to paint the vertices of a graph in such a way
that any two adjoined vertices, which are connecte
In this paper, we introduce an Effective algorithm to find the
shortest path in Multiple – Source Graph, by choosing the path
between the source and the distance that gives at least the length of
the path down to the sink. This algorithm is based
The all-nodes shortest paths problem is undoubtedly one of
the most basic problems in algorithmic graph theory. In this paper,
we introduce simple and efficient algorithm for all nodes shortest
paths problem for directed (undirected) graphs. In th