基于梯形模糊中智数的最短路径求解方法
|
摘要
最短路径的选择是图论中的经典问题之一.复杂环境中对象之间的关系通常具有模糊性、犹豫性、不确定性和不一致性,而中智集是元素的真实程度、不确定程度及谬误程度的集合,更有能力捕捉不完全信息.基于此,基于中智集理论和图理论的中智图最短路径选择成为一个关键问题.针对边长表述为梯形模糊中智数的中智图最短路径求解问题,提出一种扩展的动态规划求解方法.利用基于梯形模糊中智数的得分函数和精确函数来比较路径长度,并给出扩展的动态规划求解最短路径方法,从而得到最短路径和最短路径长度.最后,通过两个算例验证此方法的可行性,通过与Dijkstra算法对比分析说明所提出方法的合理性和有效性,并且分析了采用不同排序方法对中智图最短路径选择的影响.
The selection of the shortest path problem is one of the classic problems in the graph theory. The relationship between objects in a complex environment usually has fuzziness, hesitancy, uncertainty and inconsistency. A neutrosophic set is characterized by the degree of truth-membership, indeterminacy-membership and falsity-membership, and is more capable of capturing incomplete information. The selection of the shortest path of the neutrosophic graph based on the theory of neutrosophic set and graph theory has become a key issue. For the shortest path problem in the neutrosophic graph, in which the edge length is assigned a trapezoidal fuzzy neutrosophic number instead of a real number, a solving method based on the extended dynamic programming is proposed. The path length is compared using the score function and the accuracy function based on the trapezoidal fuzzy neutrosophic numbers. An extended dynamic programming method for solving the shortest path problem is presented to obtain the shortest path and the shortest path length. Finally, two examples are used to verify the feasibility of this method, and the comparison and analysis with the Dijkstra algorithm illustrate the rationality and effectiveness of this method. And the impact of using different sorting methods on the selection of the shortest path of the neutrosophic graph is analyzed.
The selection of the shortest path problem is one of the classic problems in the graph theory. The relationship between objects in a complex environment usually has fuzziness, hesitancy, uncertainty and inconsistency. A neutrosophic set is characterized by the degree of truth-membership, indeterminacy-membership and falsity-membership, and is more capable of capturing incomplete information. The selection of the shortest path of the neutrosophic graph based on the theory of neutrosophic set and graph theory has become a key issue. For the shortest path problem in the neutrosophic graph, in which the edge length is assigned a trapezoidal fuzzy neutrosophic number instead of a real number, a solving method based on the extended dynamic programming is proposed. The path length is compared using the score function and the accuracy function based on the trapezoidal fuzzy neutrosophic numbers. An extended dynamic programming method for solving the shortest path problem is presented to obtain the shortest path and the shortest path length. Finally, two examples are used to verify the feasibility of this method, and the comparison and analysis with the Dijkstra algorithm illustrate the rationality and effectiveness of this method. And the impact of using different sorting methods on the selection of the shortest path of the neutrosophic graph is analyzed.
引文
[1]Smarandache F.A unifying field in logics.Neutrosophy:Neutrosophic probability,set and logic[M].Rehoboth:American Research Press,1999:10-16.
[2]Wang H,Smarandache F,Zhang Y Q,et al.Interval neutrosophic sets and logic:Theory and applications in computing[M].Hexis:Arizona,2005:4-5.
[3]Wang H B,Smarandache F,Zhang Y Q,et al Single valued neutrosophic sets[J].Multispace and Multistructure,2010,4(10):410-413.
[4]Peng J J,Wang J Q.Multi-valued neutrosophic sets and its application in multi-criteria decision-making problems[J].Neutrosophic Sets and Systems,2015,10:3-17.
[5]Ye J.Multiple-attribute decision-making method under a single-valued neutrosophic hesitant fuzzy environment[J].J of Intelligent Systems,2014,24(1):23-36.
[6]Tian Z P,Wang J,Zhang H Y,et al.Simplified neutrosophic linguistic normalized weighted Bonferroni mean operator and its application to multi-criteria decision-making problems[J].Filomat,2016,30(12):3339-3360.
[7]Deli I,Mumtaz A,Smarandache F.Bipolar neutrosophic sets and their applications based on multicriteria decision making problems advanced mechatronic systems[C]Proc of the 2015 Int Conf on Advanced Mechatronic Systems.Beijing:IEEE,2015:249-254.
[8]Biswas P,Pramanik S,Giri B C.Cosine similarity measure based multi-attribute decision-making with trapezoidal fuzzy neutrosophic numbers[J].Neutrosophic Sets and Systems,2014,8:46-56.
[9]Ye J.Trapezoidal neutrosophic set and its applicaion to multiple attribute decision-making[J].Neural Comput&Applic,2015,26(5):1157-1166.
[10]Broumi S,Bakali A,Talea M,et al.Computation of shortest path problem in a network with SV-trapezoidal neutrosophic numbers[C].Proc of the 2016 Int Conf on Advanced Mechatronic Systems.Melbourne:IEEE2017:417-422.
[11]鱼先锋.半直觉模糊图与应用[J].计算机工程与应用2016,52(18):88-91.(Yu X F.Half intuitionistic fuzzy graph and application[J].Computer Engineering and Applications2016,52(18):88-91.)
[12]李秀美,陈华友.不确定信息下模糊网络最短路径关键边问题[J].武汉理工大学学报:信息与管理工程版2013,35(1):36-39.(Li X M,Chen H Y.Critical edge of the shortest path on fuzzy traffic network in uncertain information environment[J].J of WUT:Information&Management Engineering,2013,35(1):36-39.)
[13]Deng Y,Chen Y,Zhang Y,et al.Fuzzy dijkstra algorithm for shortest path problem under uncertain environment[J].Applied Soft Computing,2012,12(3):1231-1237.
[14]Jayagowri P,Ramani G G.Using trapezoidal intuitionistic fuzzy number to find optimized path in a network[J].Advances in Fuzzy Systems,20142014(1):12.
[15]Das D,De P K.Shortest path problem under intuitionistic fuzzy setting[J].Int J of Computer Applications,2014105(1):1-4.
[16]Majumder S,Pal A.Shortest path problem on intuitionistic fuzzy network[J].Annals of Pure and Applied Mathematics,2013,5(1):26-36.
[17]Broumi S,Talea M,Bakali A,et al.Single valued neutrosophic graphs[J].J of New Theory,2016,10:86-101.
[18]Broumi S,Talea M,Bakali A,et al.Applying dijkstra algorithm for solving neutrosophic shortest path problem[C].Proc of the 2016 Int Conf on Advanced Mechatronic Systems.Melbourne:IEEE,2016:412-416.
[19]Broumi S,Talea M,Bakali A,et al.Application of dijkstra algorithm for solving interval valued neutrosophic shortest path problem[C].Proc of the 2016IEEE Symposium Series on Computational Intelligence Athens:IEEE,2017:1-6
[20]Broumi S,Smarandache F,Talea M,et al.An introduction to bipolar single valued neutrosophic graph theory[J]Applied Mechanics and Materials,2016,841:184-191.
[21]Broumi S,Bakali A,Talea M,et al.Shortest path problem under bipolar neutrosphic setting[J].Applied Mechanics and Materials,2016,859:59-66.
[22]Broumi S,Talea M,Bakali A,et al.Interval valued neutrosophic graphs[J].Critical Review,2016,X:5-33.
[23]Broumi S,Bakali A,Talea M,et al.Shortest path problem under triangular fuzzy neutrosophic information[C].Proc of the 2016 10th Int Conf on Software,Knowledge Information Management&Applications.Chengdu:IEEE,2017:1-6.
[24]Broumi S,Talea M,Bakali A,et al.Shortest path problem under trapezoidal neutrosophic information[C].Proc of the Computing Conf.London:IEEE,2017:142-148.
[25]Torra V.Hesitant fuzzy sets[J].Int J of Intelligent Systems,2010,25(6):529-539.
[26]Torra V,Narukawa Y.On hesitant fuzzy sets and decision[C].Proc of the 18th IEEE Int Conf on Fuzzy Systems.Jeju Island:IEEE,2009:1378-1382.
[27]Xia M M,Xu Z S.Hesitant fuzzy information aggregation in decision making[J].Int J of Approximate Reasoning2011,52(3):395-407.
[28]Xia M M,Xu Z S,Zhu B.Generalized intuitionistic fuzzy bonferroni means[J].Int J of General Systems,201127(1):23-47.
[29]Chen N,Xu Z S,Xia M M.The electre i multi-criteria decision-making method based on hesitant fuzzy sets[J]Int J of Information Technology&Decision Making2015,14(3):621-657.
[30]Peng J J,Zhou H,Chen X H,et al.A multi-criteria decision-making approach based on TODIM and choquet integral within a multiset hesitant fuzzy environment[J]Applied Mathematics&Information Sciences,20159(4):2087-2097.
[31]Biswas P,Pramanik S,Giri B C.Value and ambiguity index based ranking method of single-valued trapezoidal neutrosophic numbers and its application to multi-attribute decision making[J].Neutrosophic Sets and Systems,2016,12:127-138.
[2]Wang H,Smarandache F,Zhang Y Q,et al.Interval neutrosophic sets and logic:Theory and applications in computing[M].Hexis:Arizona,2005:4-5.
[3]Wang H B,Smarandache F,Zhang Y Q,et al Single valued neutrosophic sets[J].Multispace and Multistructure,2010,4(10):410-413.
[4]Peng J J,Wang J Q.Multi-valued neutrosophic sets and its application in multi-criteria decision-making problems[J].Neutrosophic Sets and Systems,2015,10:3-17.
[5]Ye J.Multiple-attribute decision-making method under a single-valued neutrosophic hesitant fuzzy environment[J].J of Intelligent Systems,2014,24(1):23-36.
[6]Tian Z P,Wang J,Zhang H Y,et al.Simplified neutrosophic linguistic normalized weighted Bonferroni mean operator and its application to multi-criteria decision-making problems[J].Filomat,2016,30(12):3339-3360.
[7]Deli I,Mumtaz A,Smarandache F.Bipolar neutrosophic sets and their applications based on multicriteria decision making problems advanced mechatronic systems[C]Proc of the 2015 Int Conf on Advanced Mechatronic Systems.Beijing:IEEE,2015:249-254.
[8]Biswas P,Pramanik S,Giri B C.Cosine similarity measure based multi-attribute decision-making with trapezoidal fuzzy neutrosophic numbers[J].Neutrosophic Sets and Systems,2014,8:46-56.
[9]Ye J.Trapezoidal neutrosophic set and its applicaion to multiple attribute decision-making[J].Neural Comput&Applic,2015,26(5):1157-1166.
[10]Broumi S,Bakali A,Talea M,et al.Computation of shortest path problem in a network with SV-trapezoidal neutrosophic numbers[C].Proc of the 2016 Int Conf on Advanced Mechatronic Systems.Melbourne:IEEE2017:417-422.
[11]鱼先锋.半直觉模糊图与应用[J].计算机工程与应用2016,52(18):88-91.(Yu X F.Half intuitionistic fuzzy graph and application[J].Computer Engineering and Applications2016,52(18):88-91.)
[12]李秀美,陈华友.不确定信息下模糊网络最短路径关键边问题[J].武汉理工大学学报:信息与管理工程版2013,35(1):36-39.(Li X M,Chen H Y.Critical edge of the shortest path on fuzzy traffic network in uncertain information environment[J].J of WUT:Information&Management Engineering,2013,35(1):36-39.)
[13]Deng Y,Chen Y,Zhang Y,et al.Fuzzy dijkstra algorithm for shortest path problem under uncertain environment[J].Applied Soft Computing,2012,12(3):1231-1237.
[14]Jayagowri P,Ramani G G.Using trapezoidal intuitionistic fuzzy number to find optimized path in a network[J].Advances in Fuzzy Systems,20142014(1):12.
[15]Das D,De P K.Shortest path problem under intuitionistic fuzzy setting[J].Int J of Computer Applications,2014105(1):1-4.
[16]Majumder S,Pal A.Shortest path problem on intuitionistic fuzzy network[J].Annals of Pure and Applied Mathematics,2013,5(1):26-36.
[17]Broumi S,Talea M,Bakali A,et al.Single valued neutrosophic graphs[J].J of New Theory,2016,10:86-101.
[18]Broumi S,Talea M,Bakali A,et al.Applying dijkstra algorithm for solving neutrosophic shortest path problem[C].Proc of the 2016 Int Conf on Advanced Mechatronic Systems.Melbourne:IEEE,2016:412-416.
[19]Broumi S,Talea M,Bakali A,et al.Application of dijkstra algorithm for solving interval valued neutrosophic shortest path problem[C].Proc of the 2016IEEE Symposium Series on Computational Intelligence Athens:IEEE,2017:1-6
[20]Broumi S,Smarandache F,Talea M,et al.An introduction to bipolar single valued neutrosophic graph theory[J]Applied Mechanics and Materials,2016,841:184-191.
[21]Broumi S,Bakali A,Talea M,et al.Shortest path problem under bipolar neutrosphic setting[J].Applied Mechanics and Materials,2016,859:59-66.
[22]Broumi S,Talea M,Bakali A,et al.Interval valued neutrosophic graphs[J].Critical Review,2016,X:5-33.
[23]Broumi S,Bakali A,Talea M,et al.Shortest path problem under triangular fuzzy neutrosophic information[C].Proc of the 2016 10th Int Conf on Software,Knowledge Information Management&Applications.Chengdu:IEEE,2017:1-6.
[24]Broumi S,Talea M,Bakali A,et al.Shortest path problem under trapezoidal neutrosophic information[C].Proc of the Computing Conf.London:IEEE,2017:142-148.
[25]Torra V.Hesitant fuzzy sets[J].Int J of Intelligent Systems,2010,25(6):529-539.
[26]Torra V,Narukawa Y.On hesitant fuzzy sets and decision[C].Proc of the 18th IEEE Int Conf on Fuzzy Systems.Jeju Island:IEEE,2009:1378-1382.
[27]Xia M M,Xu Z S.Hesitant fuzzy information aggregation in decision making[J].Int J of Approximate Reasoning2011,52(3):395-407.
[28]Xia M M,Xu Z S,Zhu B.Generalized intuitionistic fuzzy bonferroni means[J].Int J of General Systems,201127(1):23-47.
[29]Chen N,Xu Z S,Xia M M.The electre i multi-criteria decision-making method based on hesitant fuzzy sets[J]Int J of Information Technology&Decision Making2015,14(3):621-657.
[30]Peng J J,Zhou H,Chen X H,et al.A multi-criteria decision-making approach based on TODIM and choquet integral within a multiset hesitant fuzzy environment[J]Applied Mathematics&Information Sciences,20159(4):2087-2097.
[31]Biswas P,Pramanik S,Giri B C.Value and ambiguity index based ranking method of single-valued trapezoidal neutrosophic numbers and its application to multi-attribute decision making[J].Neutrosophic Sets and Systems,2016,12:127-138.